Znaczenie złożoności stanu w automatach i językach regularnych?

Czytam „ Łączenie zwykłych języków i złożoności opisowej ” Galiny Jiraskowej z 2009 r. Na temat złożoności państwa wynikającej z połączenia dwóch zwykłych języków (Galiny Jiraskowej), ale nie rozumiem, jakie byłyby praktyczne implikacje złożoności państwa . Pierwszą trywialną myślą, która mnie uderzyła, było to, że większa złożoność wymagałaby więcej czasu i przestrzeni od maszyny. Czy to jest poprawne? Czy są też inne miejsca, w których złożoność państwa jest istotna i znacząca?

Edycja: Złożoność stanu zwykłego języka jest najmniejszą liczbą stanów w dowolnym deterministycznym automacie skończonym (dfa) akceptującym język. Złożoność stanu niedeterministycznego języka regularnego jest definiowana jako najmniejsza liczba stanów w dowolnym niedeterministycznym automacie skończonym (nfa) dla języka.

fl.formal-languages automata-theory regular-language

— Airmine
źródło

Jasne. Edytowałem pytanie!

— Airmine

Wydaje się możliwe, że artykuł, który czytasz, do pewnego stopnia odpowiada na pytanie ...? Czy możesz podać go bardziej szczegółowo, np. Tytuł i najlepiej link do pliku pdf, jeśli jest dostępny? Złożoność stanu FSM pojawia się w wielu aplikacjach, a także ma implikacje teoretyczne ...

— od

Tak, przejrzałem gazetę i przejrzałem referencje. Nie można znaleźć wiele związanych z zastosowaniami złożoności stanu.

— Airmine,

prawie każda aplikacja FSM (której jest wiele) musi brać pod uwagę złożoność stanu w przypadku nieistotnych „dużych” problemów. przykład. FSM są używane do rozpoznawania mowy, gdzie stany są fonemami, co może prowadzić do dużych FSM. FSM są również szeroko stosowane w aplikacjach EE, np. Obwodach itp. Tam FSM o dużej złożoności jest obwodem „dużym”. jednak w omawianej pracy skupiono się głównie na teoretycznej złożoności problemu, w którym górne / dolne granice „wysadzenia” lub „efektywnej minimalizacji” (kompresji) są kluczowymi właściwościami do badania ....

— dniu

Nie do końca „praktyczne”, ale złożoność stanu odgrywa rolę w wnioskowaniu na podstawie automatów skończonych opartych na różnorodności przez Rivest i Schapire: [konferencja ; czasopismo ].

— Neal Young,

Odpowiedzi:

Złożoność stanu tak naprawdę polega na zwięzłym opisie obiektu (w tym przypadku zwykłym języku), a nie na złożoności obliczeniowej. Temat ogólny w literaturze nazywa się „złożonością opisową” i częściowo czerpie inspirację z klasycznego artykułu Meyera i Fischera z 1971 r. Zatytułowanego „Gospodarka ekspresji automatów, gramatyk i systemów formalnych” (patrz http: // people) .csail.mit.edu / meyer / economy-of-description.pdf ). Jest to nadal obszar aktywny, z coroczną konferencją (DCFS - Descriptional Complexity of Formal Systems).

Jeśli chodzi o aplikacje, w każdym miejscu, w którym program zasadniczo opiera się na maszynie o stanie skończonym (np. Parserach), dobrze jest mieć tę maszynę o stanie skończonym jak najmniejszą.

— Jeffrey Shallit
źródło

W porządku Więc w zasadzie zmniejszenie złożoności stanu pomaga osiągnąć minimalną reprezentację danego języka, a nie ułatwia przetwarzanie?

— Airmine,

Ponadto, ponieważ większość algorytmów automatów zależy bezpośrednio od złożoności stanu, minimalizacja stanów często odbywa się z ukrytym motywem minimalizacji złożoności obliczeniowej.

— Denis,

Dodaję konkretny przykład do doskonałej odpowiedzi Jeffreya Shallita.

Załóżmy, że chcesz utworzyć słownik Scrabble (TM). Możesz wymyślić kilka sposobów reprezentowania słownika, takich jak lista słów, prób (drzewa liter) lub deterministyczne automaty. Według [1], minimalizowanie trie do świtu [= DFA] zapewnia niesamowite oszczędności przestrzeni; liczba węzłów została zmniejszona z 117 150 do 19 853. Leksykon reprezentowany jako lista słów surowych zajmuje około 780 kilobajtów, a nasz dawg może być reprezentowany w 175 kilobajtach.

Jak widać, złożoność stanu naprawdę ma znaczenie w tym przypadku, szczególnie jeśli chcesz napisać skuteczny program, tak jak zrobili to autorzy.

[1] Appel and Jacobson The Fastest Scrabble Programme na świecie , Komunikacja ACM 31 , 572-578 (1988).

— J.-E. Kołek
źródło

Dowód na to, czy można rozstrzygnąć, czy dowolna deterministyczna gramatyka bezkontekstowa (lub równoważnie deterministyczny automat wypychający) ma równoważny automat skończony opisujący ten sam język, jest zasadniczo dowodem złożoności stanu automatów skończonych opisujących deterministyczne języki bezkontekstowe: ograniczenie wielkości tych automatów skończonych w kategoriach automatów deterministycznych wyznacza granice długości procedury decyzyjnej.

Aby uzyskać szczegółowe informacje, zobacz „ Regularność i powiązane problemy dla deterministycznych automatów wypychających ” . Leslie G. Valiant.

— Alex ten Brink
źródło