Linguagens Formais e Autômatos
2012.2 – Lista 1
Profs. Alexandre Rademaker e Bruno Lopes
1. Apresente uma gramática para a linguagem L = {a n b n c n | n ≥ 0}.
2. Seja R = {(1, 2), (2, 2), (2, 3)} uma relação no conjunto {1, 2, 3}. Apresente as relações R ∗ e R + .
3. Desenvolva uma gramática para expressões lógicas, com parênteses quando necessário, operadores (∧, ∨, →, ¬)
e apenas uma variável x. As seguintes expressões são exemplos de palavras válidas: x ∧ (x ∨ x), x → (¬x ∨ x).
4. Dê um exemplo de relação que seja simétrica e transitiva mas não reflexiva.
5. Na gramática G = (V, T, P, N ) onde V = {N , D}, T = {0, 1, . . . , 9} e P = {N → D, N → D N , D → 0 | 1 | . . . | 9}. Modifique a gramática para que palavras iniciadas ou terminadas com zero não sejam válidas, isto é, não estejam na
linguagem L(G).
6. Desenvolva autômatos finitos determinísticos que reconheçam as seguintes linguagens sobre Σ = {a, b}:
(a) {w | w possui número ímpar de a e número ímpar de b}
(b) {w | w possui número par de a e impar de b ou o inverso}
(c) {w | w o quinto símbolo da direita para a esquerda de w é a}
7. Exiba uma derivação da palavra “111 1000” na gramática abaixo, indique cada regra utilizada. Justifique a existência ou não de outra derivação para a mesma palavra. Descreva em português a linguagem gerada por esta
gramática.
〈{0, 1, }, {S, X , Y ,U , Z , F }, S, R〉
onde R é o seguinte conjunto de regras:
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
S
X
U1
U0
U
Z1
Z0
Z
→
→
→
→
→
→
→
→
XY
X1U | X0Z | F
1U
0U
1
1Z
0Z
0
(i)
(j)
(k)
(l)
(m)
(n)
F1
F0
F
0FY
1FY
FY
→
→
→
→
→
→
1F
0F
F
1
FY0
1
8. Complete a prova de equivalência entre AF N e AF D.
9. Construa AFD’s a partir dos AFN’s abaixo onde σ1 e σ2 são dados na Figura 1.
(a) M 1 = ({p, q, r, s}, {0, 1}, σ1 , p, {s})
(b) M 2 = ({p, q, r, s}, {0, 1}, σ2 , p, {q, s})
σ1
p
q
r
s
0
p,q
r
s
s
1
p
r
s
σ2
p
q
r
s
0
q,s
r
s
Figura 1: Autômatos AFN’s
1
q
q,r
p
p