Matematica FIannceira

LFA Lista de Exercícios

Questão 1: Mostre que a seguinte gramática  G = (V, T, P, S) é ambígua.

V = {S}

T = {(, )}

P = { S → SS | e | (S) }

Questão 2: Considere as seguintes linguagens definidas sobre o alfabeto Σ = {a, b, c}

L1 (w) = {w | w = a*b+ (a|b)n c | n > 0 }

L2(w) = {w | w = ambn (a|b)k c| m, n, k > 0 }

L3(w) = {w | w = anbm (a|b)n c| m > 1, n > 0 }

Pede-se:

I – Classifique L1, L2 e L3 segundo a hierarquia de Chomsky.

L1:_____________________; L2:_________________; L3:_______________________

II – Complete a seguinte tabela:

Linguagem	Gramática	Máq. Reconhecedora.	Aplicação
Regular
Livre de Contexto
Dep. de Contexto
Irrestrita

Questão 3: Considere cada uma das gramática G definida pelas regras de produção apresentadas abaixo, em que os símbolos não-terminais são S, X e Y, e os símbolos terminais são a e b. S é o símbolo inicial. Classifique-as segundo a hierarquia de Chomsky. Observação: as duas gramáticas são passíveis de serem classificadas segundo a hierarquia de Chomsky

a) P1 = { S→ XY | Y

XY→ XXY

X→ a

Y→ b }

b) P2 = { S→ XY | Y

X→ XXY

X→ a

Y→ b }

Questão 4  Considere a seguinte gramática G = (V, T, P, S) com V = {a, b, c} e

P = { S → a S a |  b S b | c ) a qual gera a linguagem  L(x)  = {x = wcwR | x ∈ {a, b}* } O autômato correspondente, é M = ({p, q), T, V, Δ, p, {q}), com:

T = {a, b}; V = {S, aSa, bSb, a, b, c}; p é estado inicial e q é estado final;

 Δ = {((p, ε, ε), (q, S)), ((q, ε, S), (q, aSa)), ((q, ε, S), (q, bSb)), ((q, ε, S), (q, c)), ((q, a, a), (q, ε)), ((q, b, b), (q, ε)), {((q, c, c), (q, ε))}

Pede-se a seqüência de movimentos do autômato  M para a cadeia abbcbba.

Questão 5 : Assinale a linguagem L definida sobre o alfabeto A = {a, b, c, d} que não pode ser reconhecida por um autômato com uma pilha:

a ) L = {w | w = an bn cm , n > 0, m>0}

b ) L = {w | w = an bn cn dm , n > 0, m> 0}

c ) L = {w | w = an bm cn dl , n > 0, m> 0, l >0}

d ) L = {w | w = an bn cm dm , n > 0, m > 0}

e ) L = {w | w = an bm cm dn , n > 0, m > 0}

Questão 6  Elabore um autômato finito determinístico que reconheça as seguintes Linguagens:

1. L(w) = {w | w =(a|b)+ (ab)*}
2. L(w) = {w | w = b+ (ab)*}

Sugestão: Primeiro desenhe o autômato não-determinístico e depois aplique o algoritmo para transformá-lo em determinístico.