7/23/2019 listadeAPs
1/3
Autmatos de Pilha
1. Para cada linguagem a seguir, construa um APD, se possvel. Se no for possvel,
construa um APN (se possvel).
a. {an
!
cn"!
# n, ! $%.. {ann"!c!# n, ! $%.
c. {an!# n ! &n%.
d. {' {a, % # a uantidade de a em ' * igual + uantidade de em ' mais 1%.
e. {' {a, % # a uantidade de a em ' * igual ao doro da uantidade de em
'%.
f. {' {a, , c% # a uantidade de a em ' * igual + soma da uantidade de mais
a uantidade de c%.
g. {anncmdm"# n $, m 1%.
-. {ainci# i $, n 1%.
i. {($1)n
(1$)n
# n $%.. {($1)n$(1$)n# n $%.
!. {$n1n$!# n $, ! 1%.
l. {$n1n1!# n $, ! 1%.
m. {$n1m# m n%.
n. {$n1m/ # m n%.
Gramticas Livres de Contexto
. 0onstrua 203s para as linguagens4
a. {an!cn"!# n, ! $%.
. {ann"!c!# n, ! $%.
c. {an!# n ! &n%.
d. {anncmdm"# n $, m 1%.
e. {ainci# i $, n 1%.
f. {am"n"1nc&m# m,n $%.
g. {an&n"!c&!# n, ! $%.
-. {anmc!# m 5 n ou n !%.
&. Sea a gram6tica 4
P 57 A8 # aa8A 57 a # Aa
8 57
a. 9ue linguagem * gerada por :
. ;ostre ue * amgua.
7/23/2019 listadeAPs
2/3
c. 0onstrua uma gram6tica no amgua euivalente a .
. 0onstrua uma gram6tica euivalente + gram6tica a seguir sem vari6veis in?teis.
S 57 a # aA # 8 # 0
A 57 a8 #
8 57 Aa
0 57 c0DD 57 ddd
@. limine as regras da gram6tica a seguir4
P 57 A8 # a8
A 57 888 # a8 #
8 57 a # aA #
B. limine as regras da gram6tica a seguir
S 57 Aa8 # aa8A 57
8 57 A #
C. Sea a gram6tica4
P 57 AAA # 8
A 57 aA # 8 # 80
8 57
0 57 80
a. Se eistirem smolos in?teis, elimineos.
. limine regras .
c. limine regras unit6rias.
d. Eten-a uma 20 euivalente na forma normal de 0-oms!F.
G. Sea a gram6tica4
S 57 $A$ # 181 # 88
7/23/2019 listadeAPs
3/3
A 57 0
8 57 S # A
0 57 S #
a. Se eistirem smolos in?teis, elimineos.
. limine regras .
c. limine regras unit6rias.d. Eten-a uma 20 euivalente na forma normal de 0-oms!F.
1$. Sea a gram6tica4
S 57 aA8
A 57 A8 #
8 57 8Aa #
0 57 80
Eten-a uma 20 euivalente na forma normal de 0-oms!F.
Lema do Bombeamento e propriedade de linguagens
11. Hse o lema do omeamento para mostrar ue { annan# n $% no * uma linguagem
livre do conteto.
1. ;ostre ue so ou ue no so linguagens livres do conteto4
a. {' {a, , c% # na(') I n(')%.
. {' {a, , c% # na(') 5 n(') 5 nc(')%.
c. { amnc!# m I n I !%.
1&. ;ostre ue sim ou ue no4 as linguagens livres do conteto so fec-adas so4
a. DiferenJa.. DiferenJa sim*trica.
1
Recommended