Liczenie słów przyjętych przez zwykłą gramatykę

26

W przypadku zwykłego języka (NFA, DFA, gramatyki lub wyrażenia regularnego), jak można policzyć liczbę słów akceptowanych w danym języku? Interesujące są zarówno „z dokładnie n literami”, jak i „z najwyżej n literami”.

Margareta Ackerman ma dwa artykuły na powiązany temat wyliczania słów zaakceptowanych przez NFA, ale nie byłem w stanie zmodyfikować ich, aby liczyć wydajnie.

Wydaje się, że ograniczona natura zwykłych języków powinna ułatwić ich liczenie - prawie oczekuję formuły bardziej niż algorytmu. Niestety moje wyszukiwania jak dotąd niczego nie znalazły, więc muszę używać niewłaściwych terminów.

Charles
źródło
Zakładam, że masz na myśli „liczbę zaakceptowanych słów o rozmiarze ” lub coś w tym rodzaju? w przeciwnym razie jaka jest liczba akceptowanych słów dla Σ nΣ
Suresh Venkat

Odpowiedzi:

37

Dla DFA, w którym stan początkowy jest stanem , liczba słów o długości k , które kończą się w stanie , że jest K [ 0 , I ] , w którym macierz przeniesienia DFA (macierz, w której liczba w wierszu i oraz kolumnie j to liczba różnych symboli wejściowych, które powodują przejście ze stanu i do stanu j ). Możesz więc liczyć, że akceptujesz słowa o długości dokładnie k , nawet gdy k0kiAk[0,i]Aijijkk jest umiarkowanie duży, po prostu przez obliczenie mocy macierzy i dodanie wpisów odpowiadających stanom akceptacji.

To samo działa w przypadku przyjmowania słów o długości co najwyżej , z nieco inną matrycą. Dodaj dodatkowy wiersz i kolumnę macierzy, jeden w komórce, który jest zarówno w wierszu, jak i kolumnie, jeden w nowym wierszu i kolumnie stanu początkowego oraz zero we wszystkich pozostałych komórkach. Efektem tej zmiany w macierzy jest dodanie jednej ścieżki do stanu początkowego przy każdej mocy.k

To nie działa dla NFA. Podejrzewam, że najlepszą rzeczą jest konwersja do DFA, a następnie zastosowanie algorytmu zasilania macierzy.

David Eppstein
źródło
2
Idealna odpowiedź: oczywista dopiero po przeczytaniu.
Charles,
1
Podejście to ma wykładniczy czas działania w najgorszym przypadku, jeśli wprowadzono dane inne niż DFA. Czy to nie jest dla ciebie problem @Charles? Wydaje się, że w pytaniach zawierają wyrażenia regularne, NFA i gramatykę, a także pytają o skuteczny sposób.
Raphael
17

A=(Q={q1,,qn},Σ,δ,QF)q1QFQδQ×Σ×Q

Qi(z)qin[zn]Qi=|{w|w|=nw accepted from qi}|

Wyraźnie:

Qi(z)=[qiQF]+(qi,a,qj)δxQj(z)

Q1[zn]Q1

Wraca to do techniki wprowadzonej do gramatyki przez Chomsky'ego i Schützenbergera (1963); łatwo przenosi się do automatów skończonych.

εxaΣwΣkxxk

Raphael
źródło
Doceniam nutę historyczną!
Charles
1
Eee, w rzeczywistości jest to metoda, która działa naprawdę dobrze (i jest prosta, gdy już ją dostaniesz) w wielu okolicznościach. Na przykład możesz wykonywać CFG w dokładnie taki sam sposób.
Raphael
1
Rozumiem, źle zrozumiałem. W takim przypadku, jeśli chcesz przeczytać o tym, polecam Kuich (1970), który uważam za bardziej dostępny niż praca C&S. On także opisuje to w swojej książce, której nie pamiętam.
Raphael
1
n
1
@joro W przypadku jednoznacznych gramatyk uważam, że to prawda, tak.
Raphael,
7

Myślę, że jest to trudny problem z liczeniem, zobacz ten artykuł: Liczenie wielkości regularnych sekwencji o danej długości jest # P-zupełne: S. Kannan, Z. Sweedyk i SR Mahaney. Zliczanie i losowe generowanie ciągów w zwykłych językach. W sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA), strony 551–557, 1995.

Miklós István
źródło
1
Powyższy post zakłada, że ​​podana długość jest jednoargumentowa. Jeśli zamiast tego długość jest binarna, problem dotyczy PSPACE. Mówię to na podstawie dowodu, że decyzja o równoważności dwóch wyrażeń regularnych jest trudna w PSPACE. W ramach tej redukcji zbudowano jeden reg-ex, aby zaakceptować wszystkie ciągi, a drugi, aby zaakceptować wszystkie ciągi, które nie są poprawne, odrzucając historię obliczeń maszyny M PSPACE na wejściu w. Użycie tego drugiego wyrażenia regularnego i długości historii obliczeń M na w jako danych wejściowych do omawianego problemu sprawia, że ​​ten drugi problem również jest trudny w PSPACE.
Michaił Rudoy
3

#NC1

SamiD
źródło