Máquinas para linguagens livres de contexto que não ganham força extra por não-determinismo

21

Ao considerar os modelos de máquinas computacionais, a hierarquia de Chomsky é normalmente caracterizada por (em ordem), autômatos finitos, autômatos push-down, autômatos de ligação linear e Máquinas de Turing.

Para o primeiro e o último nível 1 (linguagens regulares e linguagens recursivamente enumeráveis), não faz diferença para o poder do modelo se consideramos máquinas determinísticas ou não determinísticas, ou seja, DFAs são equivalentes a NFAs e DTMs equivalentes a MNTs 2 .

No entanto, para PDAs e LBAs, a situação é diferente. Os PDAs determinísticos reconhecem um conjunto estritamente menor de idiomas que os PDAs não determinísticos. Também é uma questão em aberto significativa se os LBAs determinísticos são tão poderosos quanto os LBAs não determinísticos ou não [1].

Isso leva à minha pergunta:

Existe um modelo de máquina que caracteriza as linguagens livres de contexto, mas para as quais o não determinismo não adiciona poder extra? (Caso contrário, existe alguma propriedade de CFLs que sugira uma razão para isso?)

Parece improvável (para mim) que seria provável que as linguagens sem contexto precisassem de alguma forma não deterministas, mas não parece haver um modelo de máquina (conhecido) para o qual as máquinas determinísticas sejam suficientes.

A questão da extensão é a mesma, mas para linguagens sensíveis ao contexto.

Referências

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

Notas de rodapé

  1. Pergunta secundária para os comentários: existe uma razão para os níveis (ordenados por inclusão de conjunto) da hierarquia de Chomsky serem o número 3 a 0, em vez de 0 a 3?
  2. Para ser claro, estou falando sobre os idiomas que podem ser reconhecidos apenas. Obviamente, questões de complexidade são radicalmente afetadas por essa mudança.
formal-languages computability context-free computation-models context-sensitive Luke Mathieson
fonte
1
Então, você está pedindo uma classe de idiomas maior que (mas o mais próximo possível) das CFLs para as quais a versão determinística = versão não determinística?
Ryan
@ Ryan não, estou perguntando se existe um modelo de máquina que caracterize as lâmpadas fluorescentes compactas, mas para as quais variações não determinísticas e determinísticas são equivalentes em potência. No entanto, supondo que não haja uma resposta positiva (que eu suspeito que não exista), essa é uma boa questão a seguir.
Luke Mathieson
3
Eu acho que o principal problema com a questão é a falta de uma definição geral para um "modelo computacional". Você pode, por exemplo, definir uma TM determinística equipada com uma gramática livre de contexto, que aceite uma palavra se a gramática a gerar. Este é um modelo determinista que é equivalente a CFL, mas é bobagem ...
Shaull
@ Shaull, esse é um argumento justo, mas parece difícil definir o modelo "sensato". Seu exemplo obviamente parece antinatural, mas não creio que exista uma maneira justificável de defini-lo.
Luke Mathieson
Para vincular a pergunta de Ryan , a máquina mencionada na resposta de Thomas Klimpel (embora não tão elegante quanto um PDA) se encaixaria na idéia de "natural" de uma maneira que uma MT restrita à computação de um CFG não. Talvez a intuição seja que uma TM com um CFG esteja codificando explicitamente na definição de uma CFL, embora não seja óbvio, por exemplo, que CFGs e PDAs devam estar relacionados, o PDA é uma extensão natural dos DFAs e funciona para CFLs. .
Luke Mathieson

Respostas:

-2

No meu entendimento da teoria da computação, a única situação de não-determinismo não oferece flexibilidade extra (isto é, poder) está no nível recursivamente enumerável / recursivo. Isso se deve principalmente ao problema de interrupção e às limitações dos recursos de decisão da MT, que acredito que isso responda a uma de suas perguntas nas notas de rodapé e na barra lateral. A Hierarquia de Chomsky é uma representação lógica da subida da flexibilidade (se assim posso dizer), permitindo mais força à máquina. Isso ajuda alguém com suas perguntas / pensamentos?

Quanto aos PDAs e LBAs, terei outras pessoas bem-sucedidas aqui na comunidade para ajudar nisso, minha experiência tem sido mais com TMs e com a teoria associada à parte mais alta (mais ER) da hierarquia (pelo menos como ensinado em minha graduação).

Teoria da computação de Peter Linz

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

bmc
fonte
Isso não responde à pergunta. O OP já está ciente do que você escreveu.
Yuval Filmus