UCPEL/ESIN/BCC
058814 Linguagens Formais e Autômatos
Prof. Luiz A M Palazzo
Lista de Exercícios Número 2
1. Definir:
a)
b)
c)
d)
Gramática
Derivação
Linguagem Gerada
Gramáticas Equivalentes
2. O que é uma Linguagem Regular ou do Tipo 3?
3. Quais os três tipos de formalismos empregados no estudo de linguagens
regulares ou do tipo 3? Exemplifique cada um deles.
4. Seja M = (Σ, Q, δ, q0, F) um AFD. A função programa estendida,
denotada por: δ: Q x Σ* → Q é a função programa δ: Q x Σ → Q,
estendida para palavras. Dê a definição indutiva da função programa
estendida.
5. Compare autômatos finitos determinísticos (AFD), não determinísticos (AFN)
e com movimento vazio (AFε). Especifique formalmente qual a diferença
entre eles.
6. Construa o diagrama do autômato finito M6 definido abaixo, diga a que
classe o autômato pertence e qual a linguagem L6 que ele reconhece:
M6 = ( {a, b}, {q0, qf}, δ, q0, {qf}), onde δ é dada pela tabela abaixo:
δ,
q0
qf
a
{q0, qf}
{qf}
b
{qf}
-
7. Dado o diagrama abaixo, construa a definição do autômato M7
correspondente. Diga a que classe pertence o autômato e qual a linguagem
L7 que ele reconhece.
q0
a, b
a
q1
a
qf
a, b
8. Construa a definição do AFN M8 que reconhece a linguagem L8 = {w | w
começa e termina por a e possui bb como subpalavra}
9. Desenvolver AFDs que reconheçam as linguagens abaixo sobre Σ = {a, b}:
a) {w | w possui aaa como subpalavra}
b) {w | o sufixo de w é aa}
c) {w | w possui um número ímpar de a e b}
d) {w | w possui número par de a e ímpar de b ou vice-versa}
e) {w | o quinto símbolo da esquerda para a direita de w é a}
10. Diga se são verdadeiras ou falsas as seguintes equivalências. Justifique sua
resposta:
a) (a* + b)* = (b* + a)*
b) (b* + a*)* = (b + a)*
11. Construa os diagramas dos AFε que reconhecem as linguagens gerada pelas
ERs abaixo:
a) a* (b + (a + b))* b
b) a + ((ab)* + bb)*
c) (ab*aaa + bbb)* + ab
12. Descreva como e para que são empregados os formalismos operacionais
(autômatos), axiomáticos (gramáticas) e denotacionais (expressões
regulares) na representação de linguagens regulares ou do tipo 3.