Maszyny dla języków bezkontekstowych, które nie zyskują dodatkowej mocy z niedeterminizmu

21

Rozważając modele maszynowe obliczeń, hierarchię Chomsky'ego zazwyczaj charakteryzuje (w kolejności), automat skończony, automat push-down, automat liniowo związany i maszyny Turinga.

W przypadku pierwszego i ostatniego poziomu 1 (języki zwykłe i języki z wyliczaniem rekurencyjnym) nie ma różnicy w sile modelu, czy rozważamy maszyny deterministyczne czy niedeterministyczne, tj. DFA są równoważne NFA, a DTM są równoważne NTM 2 .

Jednak w przypadku urządzeń PDA i LBA sytuacja jest inna. Deterministyczne PDA rozpoznają ściśle mniejszy zestaw języków niż niedeterministyczne PDA. Istotne jest również otwarte pytanie, czy deterministyczne LBA są tak silne, jak niedeterministyczne LBA, czy nie [1].

To powoduje moje pytanie:

Czy istnieje model maszyny, który charakteryzuje języki bezkontekstowe, ale dla których niedeterminizm nie dodaje żadnej dodatkowej mocy? (Jeśli nie, czy istnieje jakaś właściwość świetlówek kompaktowych, która sugeruje przyczynę tego?)

Wydaje mi się mało prawdopodobne (dla mnie), aby udowodniono, że języki bezkontekstowe w jakiś sposób potrzebują niedeterminizmu, ale wydaje się, że nie ma (znanego) modelu maszyny, dla którego wystarczające byłyby deterministyczne maszyny.

Pytanie o rozszerzenie jest takie samo, ale dotyczy języków kontekstowych.

Bibliografia

  1. S.-Y. Kuroda, „Classes of Languages ​​and Linear Bound Automata” , Information and Control, 7: 207-223, 1964.

Przypisy

  1. Boczne pytanie do komentarzy, czy istnieje powód, dla którego poziomy (uporządkowane według włączenia zestawu) hierarchii Chomsky'ego mają być od 3 do 0, zamiast od 0 do 3?
  2. Mówiąc wprost, mówię tylko o językach, które można rozpoznać. Taka zmiana radykalnie wpływa na pytania o złożoność.
formal-languages computability context-free computation-models context-sensitive Luke Mathieson
źródło
1
Pytasz więc o klasę języków większych niż (ale jak najbliżej) świetlówek kompaktowych, dla których wersja deterministyczna = wersja niedeterministyczna?
Ryan
@ Ryan nie, pytam, czy istnieje model maszyny, który charakteryzuje CFL, ale dla którego niedeterministyczne i deterministyczne warianty mają równoważną moc, Jednak zakładając, że nie ma pozytywnej odpowiedzi (której, jak podejrzewam, nie ma), to dobrze pytanie uzupełniające.
Luke Mathieson
3
Myślę, że głównym problemem tego pytania jest brak ogólnej definicji „modelu obliczeniowego”. Można na przykład zdefiniować deterministyczną bazę TM, która jest wyposażona w bezkontekstową gramatykę, która akceptuje słowo, które generuje gramatyka. Jest to model deterministyczny, który jest równoważny CFL, ale jest głupi ...
Shaull
@Shaull, to słuszna kwestia, ale wydaje się, że trudno jest zdefiniować „rozsądny” model. Twój przykład jest oczywiście nienaturalny, ale nie sądzę, aby istniało uzasadnione rozwiązanie tego problemu.
Luke Mathieson
Aby połączyć się w kolejnym pytaniu Ryana , maszyna wymieniona w odpowiedzi Thomasa Klimpela (choć nie tak elegancka jak PDA), pasowałaby do idei „naturalnej” w sposób, w jaki TM nie ograniczałaby się do obliczania CFG. Być może intuicja jest taka, że ​​TM z CFG koduje wprost w definicji CFL, podczas gdy nie jest oczywiste, na przykład, że CFG i PDA powinny być powiązane, PDA jest naturalnym rozszerzeniem DFA i zdarza się, że działa dla CFL .
Luke Mathieson

Odpowiedzi:

-2

W moim rozumieniu teorii obliczeń jedyną sytuacją, w której niedeterminizm nie daje dodatkowej elastyczności (tj. Mocy), jest poziom rekurencyjnie wyliczalny / rekurencyjny. Wynika to przede wszystkim z problemu zatrzymania i ograniczeń możliwości TM w zakresie rozstrzygalności, co, jak sądzę, odpowiada na jedno z twoich pytań w przypisach stóp oraz pasek boczny. Hierarchia Chomsky'ego jest logiczną reprezentacją zwiększania elastyczności (jeśli tak mogę powiedzieć), pozwalając na większą moc maszyny. Czy to pomaga w twoich pytaniach / przemyśleniach?

Jeśli chodzi o PDA i LBA, inne osoby z naszej społeczności pomogą w tym, moje doświadczenie dotyczyło TM i teorii związanej z wyższą (więcej RE) częścią hierarchii (przynajmniej tak, jak nauczano w mój student).

Teoria obliczeń Petera Linza

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

bmc
źródło
To nie odpowiada na pytanie. PO jest już świadomy tego, co napisałeś.
Yuval Filmus,