[RESOLVIDO] Autômato com Pilha

Assuntos Gerais
#1

Alguém poderia me ajudar com essa questão, por favor ?

Considere a linguagem L2 = {aⁿ bⁱ cⁿ ⁺ ⁱ | n, i ≥ 0}. Monte, em forma de grafo, a função de transição de um Autômato com Pilha que reconheça L2

#2

Algumas dicas:

  • L2 contém uma string vazia, pois n e i podem ser zero;
  • Enquanto estiver lendo a’s, empilhe A’s;
  • Ao passar para o reconhecimento dos b’s da fita, empilhe B’s;
  • Ao passar para o reconhecimento dos c’s da fita, desempilhe os A’s e os B’s, visto que a quantidade de c’s é justamente a quantidade de A’s (que representam as os a’s reconhecidos) somada à quantidade de B’s (que representam as os b’s reconhecidos);
  • Estou sugerindo A e B como símbolos da pilha, mas vc pode usar o que achar melhor;
  • Decida se o reconhecimento será feito usando pilha vazia ou estado final;
  • Não sei qual livro está usando, mas o livro do Hopcroft usa um símbolo inicial de pilha chamado Z0 enquanto o do Sipser não, o que vai interferir no item acima.

Mais algumas dicas:

  • Quais strings são aceitas pelo PDA?
    • string vazia (epsilon)
    • ac
    • aacc
    • bc
    • bbcc
    • abcc
    • aabbcccc
  • Textualmente, você pode definir essa linguagem como as strings formadas por 0 ou muitos a’s, seguidos de zero ou muitos b’s seguidos de uma quantidade de c’s que corresponde à soma da quantidade de a’s e da quantidade de b’s. É justamente essa característica “contável” que associa duas quantidades que lhe dá o indício de que essa linguagem é livre de contexto.
1 curtida
#3

Muito obrigado pelas dicas!!
Você saberia se eu posso representar assim ?

AP
AP935×652 27.4 KB

#4

Está quase lá. Essa notação é do livro do Sipser. Faltam algumas coisas:

  • E se a string for vazia?
  • E se não conter b’s, mas conter a’s (vc já fez o outro lado, se tiver b’s, mas não a’s);
#5

Acho que consegui

image
image965×680 29.2 KB

#6

Vc ta usando qual programa para desenhar as máquinas de estado? Passa pra mim por favor, dou aula disso e tenho o meu programa específico, mas é bom ter mais opções.

#7

Parece que tá ok, só faltando reconhecer a String vazia.

#8

Estou utilizando esse site online

#9

Ah, legal. Depois da uma olhada aqui: Um simulador de autômatos
Ano que vem devo continuar a implementar. Esse ano foi complicado. É um simulador que eu comecei a implementar no ano passado. Ele cobre uma parte das linguagens regulares. A simulação das livres de contexto complica um pouco por causa do não determinismo que é apresentado direto nos materiais aí eu teria q converter um PDA não determinístico para um determinístico assim como é feito com o DFA no simulador… Enfim, vamos ver se ano que vem eu continuo.

2 curtidas
#10

Você diz como se: n = 0 e i = 0 ?
E qual seria a representação de uma string vazia ?

#11

Isso. Seu PDA deve reconhecer uma string que não tem nenhum símbolo. No seu caso, vc pode ter uma transição E,$->E de q1 à q5. No material que vc está usando E é de empty (vazio) e o cifrão ($) é usado como símbolo inicial da pilha. Tem obras que chamam o símbolo e a string vazia de épsilon (ε) e já vi lambda (λ) tbm.

#12

Esta correto ?

De verdade, muito obrigado! Você é um excelente professor!
Por meio de um fórum conseguiu deixar extremamente claro o conteúdo! Quem dirá pessoalmente em uma sala de aula!

AP
AP957×682 32.1 KB

1 curtida
#13

Isso. Inclusive, se vc deixar q0 como estado de aceitação também, além de q5, e tirar a transição de q1 a q5 vc terá o mesmo resultado. Outra coisa, como estamos falando de um modelo matemático, o rigor da representação é imprescindível. Vc precisa mostrar que q0 é o estado inicial.

1 curtida
#14

Agradeço o elogio! Um abraço!

1 curtida
#15

Pq removeu as imagens e o problema?

#16