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

16

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ć

fajaN.jaT.midofasol={<sol> ∣sol to gramatyka bez kontekstu |L.(sol)|<}

Udowodnij, że fajaN.jaT.midofasol jest rozstrzygającym językiem.

i...

Pozwolić

fajaN.jaT.miT.M.={<M.> ∣M. jest maszyną Turinga z |L.(M.)|<}

Udowodnij, że fajaN.jaT.miT.M. 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 ZARmiX , gdzie

ZARmiX={<R,w> ∣R jest wyrażeniem regularnym z wL.(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 ZAdofasol również musi być rozstrzygalny, ponieważ można go przekonwertować na wyrażenie regularne. To, oraz fakt, że ZAT.M. 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 MZARmiXZAT.M.ZAT.M.

BrotherJack
źródło
5
„gramatyka wolna od kontekstu może być przekształcona na wyrażenie regularne i odwrotnie” To nieprawda (chyba że interpretujesz to jako „istnieje CFG, które można przekształcić w wyrażenie regularne”, ale nie sądzę, że to właśnie Ty Oznaczało). Gramatyki regularne można konwertować na wyrażenia regularne. Nie ma algorytmu konwertującego CFG na wyrażenia regularne z tego prostego powodu, że większość języków bezkontekstowych (tj. Wszystkie języki bezkontekstowe, które nie są również językami regularnymi) nie można opisać za pomocą wyrażeń regularnych.
sepp2k

Odpowiedzi:

9
  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 GFINITECFGFINITECFG

  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, żeFINITETMHFINITETMFINITETMHHFINITETMHHHję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.HFINITETMFINITETM

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.

Victor Stafusa
źródło
1
Mam problem z dowodem drugim. OK, więc przekazujesz H do G, tak? Jeśli G zwraca true, a H jest skończone, ma to sens. Jednak nie otrzymuję, że zestaw danych wejściowych jest nieskończony, do jakiego wejścia się odwołujesz?
BrotherJack
1
@BrotherJack Dane wejściowe mogą być dowolnej długości, ich długość jest nieograniczona. Może to być ciąg z jednym symbolem lub wejście o długości miliona terabajtów. W ten sposób możliwe dane wejściowe dla są zestawem nieskończonym, ponieważ możemy go dowolnie zwiększyć. HH
Victor Stafusa,
1
DOBRZE. To wydaje się mieć sens. Czy poprawne byłoby odniesienie się do tego wejścia jako „dowolnego możliwego ciągu w języku wejściowym H”?
BrotherJack
1
@BrotherJack - Zredagowałem odpowiedź, aby wyjaśnić ten punkt.
Victor Stafusa,
1
Doskonałe wyjaśnienie! Dziękuję Ci bardzo za Twój czas.
BrotherJack
2

FINITECFG

LNxLN

LLN

N2NLL

Ran G.
źródło