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