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

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.

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 $0$$k$$i$$A^k[0,i]$$A$$i$$j$$i$$j$$k$$k$ 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.

$A = (Q = \{q_1, \dots, q_n\}, \Sigma, \delta, Q_F)$$q_1$$Q_F \subseteq Q$$\delta \subseteq Q\times\Sigma\times Q$

$Q_i(z)$$q_i$$n$$[z^n]Q_i = |\{w \mid |w| = n \wedge w \text{ accepted from } q_i\}|$

Wyraźnie:

$Q_i(z) = \left[ q_i \in Q_F \right] + \sum\limits_{(q_i, a, q_j) \in \delta} x \cdot Q_j(z)$

$Q_1$$[z^n]Q_1$

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

$\varepsilon$$x$$a \in \Sigma$$w \in \Sigma^k$$x$$x^k$

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.

$\#\mathsf{NC}^1$