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
- S.-Y. Kuroda, „Classes of Languages and Linear Bound Automata” , Information and Control, 7: 207-223, 1964.
Przypisy
- 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?
- 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ść.