Zdolność rozstrzygania języków gramatyki i automatów

Uwaga: jest to pytanie związane z nauką na kursie CS na uniwersytecie, NIE jest to zadanie domowe i można je znaleźć tutaj pod egzaminem Fall 2011.

Oto dwa pytania, na które patrzę z poprzedniego egzaminu. Wydaje się, że są ze sobą powiązane, pierwsze:

Pozwolić

$\qquad \mathrm{FINITE}_{\mathrm{CFG}} = \{ < \! G \! > \mid G \text{ is a Context Free Grammar with } |\mathcal{L}(G)|<\infty \}$

Udowodnij, że $\mathrm{FINITE}_{\mathrm{CFG}}$ jest rozstrzygającym językiem.

i...

Pozwolić

$\qquad \mathrm{FINITE}_{\mathrm{TM}} = \{ < \! M\!> \mid M \text{ is a Turing Machine with } |\mathcal{L}(M)|<\infty \}$

Udowodnij, że $\mathrm{FINITE}_{\mathrm{TM}}$ jest niezdecydowanym językiem.

Trochę zagubiłem się w rozwiązywaniu tych problemów, ale mam kilka spostrzeżeń, które moim zdaniem mogą być właściwe. Pierwszą rzeczą, o której wiem, jest to, że język $A_{\mathrm{REX}}$ , gdzie

$\qquad A_{\mathrm{REX}} = \{ <\! R, w \!> \mid R \text{ is a regular expression with } w \in\mathcal{L}(R)\}$

jest rozstrzygalnym językiem (dowód znajduje się w teorii obliczeń Michaela Sipsera , str. 168). To samo źródło dowodzi również, że Gramatyka bezkontekstowa może zostać przekonwertowana na wyrażenie regularne i odwrotnie. Zatem $A_{\mathrm{CFG}}$ również musi być rozstrzygalny, ponieważ można go przekonwertować na wyrażenie regularne. To, oraz fakt, że $A_{\mathrm{TM}}$ jest un -decidable, wydaje się być związane z tym problemem.

Jedyne, o czym myślę, to przekazanie G do maszyn Turinga dla (po konwersji G do wyrażenia regularnego) i . Następnie zaakceptowanie, jeśli G robi, i odrzucenie, jeśli G nie. Ponieważ jest nierozstrzygalny, nigdy się tak nie stanie. Jakoś mam wrażenie, że popełniam tutaj błąd, ale nie jestem pewien, co to jest. Czy ktoś mógłby mi tutaj pomóc? A T M A T $A_{\mathrm{REX}}$$A_{\mathrm{TM}}$$A_{\mathrm{TM}}$

1. Konwertuj G na Chomsky Normal . W ten sposób jedyną pustą pochodną byłby symbol początkowy, który nie pojawia się nigdzie indziej, a zatem jeśli istnieje produkcja, która może być w stanie sama się wygenerować, gramatyka jest nieskończona. Jeśli taka produkcja nie istnieje, każdy symbol będzie mógł wygenerować skończony zestaw ciągów, a wtedy gramatyka będzie skończona. Zbuduj więc ukierunkowany wykres, w którym każda produkcja jest węzłem, a każdy symbol w produkcji jest krawędzią skierowaną na ten symbol. Jeśli wykres ma jakiś cykl, CFG jest nieskończony, w przeciwnym razie nie. Stąd maszyna Turinga dla mogłaby być dokładnie tak zbudowana, a wtedy jest rozstrzygalne. F I N I T E C F $FINITE_{CFG}$$FINITE_{CFG}$

2. Załóżmy, że rozstrzygalne jest . Powiedzmy, że jest maszyną Turinga, która ma jakiś ciąg jako dane wejściowe i używa siebie jako danych wejściowych do . Jeśli zwraca true (tzn. akceptuje tylko skończony język), to akceptuje dane wejściowe, co prowadzi do sprzeczności, ponieważ zestaw danych wejściowych jest nieskończony (długość danych wejściowych jest nieograniczona, więc zaakceptuj dowolny możliwy ciąg jako środek wejściowy przyjmowanie nieskończonego zestawu ciągów). Jeśli zwraca false (tzn. Język jest nieskończony), to odrzuca dane wejściowe, co oznacza, że$FINITE_{TM}$$H$$FINITE_{TM}$$FINITE_{TM}$$H$$H$$FINITE_{TM}$$H$$H$$H$język jest skończony, ponieważ nie przyjmuje żadnych danych wejściowych (tzn. jego język jest pusty), co również prowadzi do sprzeczności. W ten sposób przypuszczenie, że istnieje, prowadzi do sprzeczności, a przypuszczenie to opiera się na przypuszczeniu, że jest rozstrzygalny. Zatem, sprzecznie, mamy że nie podlega rozstrzygnięciu.$H$$FINITE_{TM}$$FINITE_{TM}$

To samo źródło dowodzi również, że Gramatyka bezkontekstowa może zostać przekonwertowana na wyrażenie regularne i odwrotnie.

Naprawdę wątpię, by Sipser stwierdził, że prawdopodobnie źle odczytałeś lub źle zrozumiałeś. Oznaczałoby to, że gramatyki bezkontekstowe generują dokładnie te same języki, co gramatyki liniowo-prawe. To nieprawda; generowane gramatyki z prawej liniowości są odpowiednim podzbiorem gramatyk bezkontekstowych dp dp. To powiedziawszy, sposób, w jaki próbowałeś używać zwykłych języków, aby odpowiedzieć na pytania, po prostu prowadzi cię do nikąd.

Jak widać powyżej w moich dowodach, dwa pytania są rzeczywiście dwoma bardzo odrębnymi, niezwiązanymi ze sobą pytaniami. Zdarza się, że zostały sformułowane podobnie.

$FINITE_{CFG}$

$L$$N$$x\in L$$N$

$L$$L$$N$

$N$$2N$$L$$L$