Por que os autômatos de empilhamento usam uma pilha?

Estou participando de uma aula de teoria da computação e meu professor nos disse que um autômato de empilhamento não pode usar estruturas de dados além de uma pilha (como uma fila ou várias pilhas). Por que é que?

Se você alterar a pilha para a fila ou várias pilhas, o poder da computação aumentará! (como você sabe, podemos modelar uma fila com duas pilhas). Se usarmos uma fila, ela poderá ser poderosa como uma máquina de Turing. No entanto, o poder computacional de um autômato push-down não é tanto! Você pode saber mais sobre isso aqui .

Existem várias camadas possíveis para sua pergunta.

• Por que os PDAs devem ter uma pilha? -- Por definição! É assim mesmo.
• Mas por que eles são definidos assim? Alguém achou que poderia ser interessante. E aparentemente aconteceu, porque muitas pessoas (leia-se: todo o campo) concordaram em usar essa definição.
• Por que isso é interessante? - Veja a resposta do reinierpost .
• Por que meu professor escolhe ensinar PDAs? - Essa é uma questão multifacetada; veja aqui para uma pergunta semelhante. As respostas continuam.

Eu gostaria de expandir um pouco a segunda bala. Como surgem diferentes definições?

Se você assumir o controle finito com diferentes modelos de memória, as classes resultantes de autômatos terão recursos muito diferentes. De fato, é uma grande parte do que a teoria dos autômatos se preocupa. Depois que você perceber que brincar com definições pode levar a conceitos interessantes, é natural para os pesquisadores - um grupo curioso! - tentar explorar o espaço dos possíveis modelos.

Para listar apenas alguns exemplos de idéias que as pessoas tiveram:

• memória finita -> regular
• pilha única -> sem contexto
• fila única -> Turing-complete
• duas pilhas -> Turing-complete
• fita infinita -> Turing-completo
• montões -> realmente não sabemos
• monoides -> todos os tipos de coisas interessantes

E assim por diante.

Observe que você também pode modificar outros elementos:

• O alfabeto - torne-o infinito ou contínuo.
• A função de transição - faça uma relação ou permita -transitions.$\varepsilon$
• O conjunto de estados - torne-o infinito ou permita vários estados iniciais.
• As entradas - torná-las infinitas, ou árvores ou sequências cronometradas.
• Restrições adicionais - use fitas, mas permita apenas movimentos em uma direção ou digitalize k vezes (direções alternadas ou sempre esquerda-direita?)

Coisas interessantes podem acontecer!

Essa é a beleza das definições matemáticas: você geralmente obtém alguma coisa . Depois, você pode gastar muitos meses para descobrir o que é que tem. Talvez seja interessante, talvez não. Talvez seja útil (uma pergunta temida depois das conversas!), Talvez não. Mas sempre é .

OmG e Raphael já responderam sua pergunta:

• autômatos de empilhamento usam uma pilha porque são definidos dessa maneira
• se eles não usassem uma pilha, o que você obteria seria um tipo diferente de autômato, com propriedades diferentes

Nesse ponto, você pode perguntar: por que meu professor apresenta o autômato de empilhamento, não algum outro tipo de autômato? O que torna o autômato de empilhamento, com uma pilha, mais interessante do que um autômato com alguma outra estrutura de dados?

A resposta é que autômatos não determinísticos de pushdown podem reconhecer exatamente as linguagens sem contexto , as linguagens geradas pelas gramáticas sem contexto , que foram introduzidas no início da história da ciência da computação, na década de 1950, como uma técnica para descrever a sintaxe. de idiomas: idiomas naturais, como inglês ou russo, e idiomas de computador, como linguagens de programação (a primeira linguagem de programação descrita foi FORTRAN ).

Isso foi um grande negócio na época. Cibernética e behaviorismo eram toda a mania. Os computadores estavam começando a ser aplicados comercialmente. Uma das áreas em que foram aplicadas foi o processamento de idiomas . Como podemos descrever a linguagem?

Bem, consiste em enunciados (coisas que as pessoas dizem ou escrevem), que consistem em sequências de itens (palavras ou sons). Uma pessoa que quer dizer algo emitirá essas declarações; outra pessoa os recebe e faz sentido com eles. E se queremos que um computador faça a mesma coisa? Precisamos encontrar uma maneira de descrever um idioma que possa ser ensinado a um computador. Precisamos de uma maneira de gerar enunciados válidos que um computador possa usar e de reconhecer esses enunciados que um computador pode usar - de modo que os enunciados sejam, na verdade, os enunciados de um idioma que os humanos usam, como inglês ou russo.

Já havia descrições de dispositivos que poderiam fazer essas coisas: havia máquinas de estado e vários tipos de autômatos. Entretanto, Noam Chomsky , lingüista matemático do MIT envolvido em um projeto de tradução mecânica , as máquinas de estado realizadas não são poderosas o suficiente para descrever idiomas naturais como o inglês, pois não podem descrever o fenômeno de recursão no idioma . Ele precisava de algo semelhante, mas com o poder de descrever a recursão, e chegou às gramáticas sem contexto . Ele provou que estas podem de fato descrever mais linguagens do que as máquinas de estado, mas menos do que algumas outras técnicas - um resultado conhecido como hierarquia de Chomsky. Ele esperava que eles descrevessem idiomas como inglês e russo.

Gramáticas livres de contexto geram expressões. Chomsky pensou que eles basicamente descreviam como uma pessoa gera sentenças ao falar. Você também precisa de um dispositivo para descrever como as declarações são reconhecidas. É para isso que servem os autômatos de empilhamento . Eles podem reconhecer exatamente os enunciados gerados por uma gramática livre de contexto. Então, eles pensavam que descreviam basicamente como um humano reconhece sentenças ao ouvir.

Logo depois, foi descoberto que as linguagens sem contexto não são capazes de descrever completamente a sintaxe das linguagens - você precisa de todos os tipos de máquinas adicionais para fazê-lo corretamente. Isso é verdade tanto para idiomas naturais quanto para idiomas artificiais. (Para ser sincero, acho que Chomsky pretendia criar linguagens visivelmente flexíveis , exceto que ele não percebia a diferença e, se tivesse, isso nos salvaria de muitos aborrecimentos.)

No entanto, linguagens sem contexto e autômatos de empilhamento são matematicamente dispositivos muito simples e elegantes, e a hierarquia de Chomsky é um resultado simples e elegante; portanto, são muito úteis na educação para explicar os conceitos básicos de reconhecimento e descrição de linguagem baseada em computador ( linguagem formal teoria ). Por esse motivo, eles continuam sendo uma parte padrão do currículo teórico de ciências da computação, e muitas técnicas usadas na prática são baseadas nelas, portanto são realmente um conhecimento necessário se você deseja estudar algo relacionado ao processamento de linguagem natural, linguagem de programação implementação e outros tópicos relacionados ao idioma.