Exercícios Teoria da computação -Pilha

Prévia do material em texto

- 1 – 
Exercícios – Autômato de Pilha 
 
(HOPCROFT 6.2.2 - adaptado) Projete um PDA para aceitar a linguagem onde o conjunto de todos os 
strings em que a quantidade de 0´s é duas vezes a quantidades de 1´s. 
 
(HOPCROFT 6.1.1) Suponha que o PDA 
      pZqXZpqP ,,,,,,1,0,, 00 
 tenha a função de 
transição a seguir: 
1. 
    00 ,,0, XZqZq 
. 
2. 
    XXqXq ,,0, 
. 
3. 
    XqXq ,,1, 
. 
4. 
     ,,, pXq 
. 
5. 
     ,,, pXp 
 
6. 
    XXpXp ,,1, 
 
7. 
     ,,1, 0 pZq 
. 
 
 (HOPCROFT 6.2.6) Considere o PDA P do exercício 6.1.1. 
PDA Exercício 6.1.1: 
 
a) Converta 
P
 em outro PDA 
1P
 que aceite por pilha vazia a mesma linguagem que 
P
 aceite pelo estado 
final; isto é, 
   PLPN 1
. 
 
b) Encontre um PDA 
2P
tal que 
   PNPL 2
; isto é, 
2P
 aceita pelo estado final o que 
P
 aceita por pilha 
vazia. 
 
 
(HOPCROFT 6.4.2 - adaptado) Forneça autômatos de pilha para aceitar as linguagens a seguir: 
 
a) 
 mnmn |10
. 
 
b) 
 mnmn |10