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.
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ą.
źródło
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).
ź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.
źródło