Autômato de Pilha para anbmcn+m

Prévia do material em texto

Um autômato com pilha é um autômato finito com uma memória auxiliar em forma de pilha. Essa pilha aumenta o poder de reconhecimento do autômato de pilha em comparação aos autômatos finitos tradicionais.
Imagine que você esteja desenvolvendo um software para reconhecimento de linguagens e precise reconhecer uma linguagem no formato anbmcn+m, ou seja, uma linguagem formada por palavras contendo uma ou mais ocorrências de letras "a", seguida de uma ou mais ocorrências de letras "b", seguida de uma sequência de letras "c" cuja quantidade deve ser igual à soma de letras "a" e "b" lidas anteriormente.
Para desenvolver esse software de reconhecimento de linguagens, ​​​​​​​use o software JFLAP para implementar um autômato de pilha determinístico para reconhecer essa linguagem.
Resposta
Será preciso criar um autômato de pilha determinístico similar ao da figura a seguir:
Para cada símbolo "a" lido na entrada, um símbolo "A" é inserido na pilha. Isso ocorrerá até que o primeiro símbolo "b" seja lido, o que fará com que um símbolo "B" seja empilhado. Esse processo se repetirá enquanto outros símbolos "b" forem lidos.
Assim que um símbolo "c" for lido, o autômato removerá da pilha os símbolos "B" que foram empilhados por último. Assim que os "B"s acabarem, o autômato procurará remover os símbolos "A". Para que o autômato chegue ao estado final e aceite a palavra fornecida, a quantidade de "c"s lida deve ser igual à quantidade de "a"s e "b"s lidos, satisfazendo, assim, à condição de aceitação.
image1.jpeg