gabarito - p1 2013.2

Prévia do material em texto

P1 — Linguagens Formais e Teoria da Computac¸a˜o, 2013.2
Prof. Christiano Braga
Instituto de Computac¸a˜o
Universidade Federal Fluminense
01/11/2013
Gabarito
1. (1 ponto) Como linguagens sa˜o formalizadas (isto e´, entendidas matematicamente) neste curso?
Resposta: Linguagens sa˜o conjuntos de palavras.
2. (1 ponto) Qual a relac¸a˜o entre autoˆmatos finitos e linguagens formais?
Resposta: Um autoˆmatos (finito) reconhece uma linguagem formal.
3. (1 ponto) Qual a relac¸a˜o entre grama´ticas e linguagens formais?
Resposta: Uma grama´tica gera (as palavras de) uma linguagem.
4. (1 ponto) Mostre porque todo autoˆmato finito determin´ıstico e´ tambe´m um autoˆmato finito
na˜o-determin´ıstico. Resposta: Um AFD e´ um caso particular de um AFN quando a func¸a˜o de
transic¸a˜o leva sempre a um conjunto unita´rio de estados.
5. (2,75 pontos) Mostre porque todo autoˆmato finito na˜o-determin´ıstico e´ tambe´m um autoˆmato
finito determin´ıstico. Exemplifique sua resposta construindo, passo a passo, o autoˆmato finito
determin´ıstico associado ao autoˆmato finito na˜o-determin´ıstico da Figura 1.
(0,25 pontos) Qual e´ a linguagem aceita pelo AFN da Figura 1?
q0
a,b
��
a // q1 a // q2
Figura 1. Autoˆmato finito na˜o-determin´ıstico
Resposta: Todo AFN tem um AFD que reconhece a mesma linguagem reconhecida pelo AFN.
Seja M = (Σ,Q, δ, q0, F ) um AFN. Constro´i-se um AFD MD = (Σ,QD, δD, {q0}, FD) da seguinte
forma:
(a) QD = 2
Q
(b) δD : QD ×Σ → QD, onde
δD({q1, . . . , qn}, a) = {p1, . . . , pm} ⇔ δ∗({q1, . . . , qn}, a) = {p1, . . . , pm}.
(c) FD ⊆ QD,∀f ∈ FD(f ∩ F 6= ∅)
A linguagem reconhecida pelo autoˆmato da Figura 1 e´ L = {w | “aa” e´ sufixo de w}. O AFD da
Figura 1 e´ constru´ıdo da seguinte forma:
(a) QD = {∅, {q0}, {q1}, {q2}, {q0, q1}, {q0, q2}, {q1, q2}, {q0, q1, q2}}
(b)
QD a b
{q0} {q0, q1} {q0}
{q1} {q2} ∅
{q2} ∅ ∅
{q0, q1} {q0, q1, q2} {q0}
{q0, q2} {q0, q1} {q0}
{q1, q2} {q2} ∅
{q0, q1, q2} {q0, q1, q2} {q0}
As linhas em cinza denotam transic¸o˜es “inu´teis”, isto e´, teˆm como estado origem (dom´ınio)
um estado inalcanc¸a´vel a partir de q0. Ce´lulas contendo ∅ denotam estados para os quais δ e´
indefinida.
(c) FD = {{q0, q1, q2}}
6. (3 pontos) Mostre, passo a passo, qual o autoˆmato finito determin´ıstico mı´nimo associado ao
autoˆmato finito determin´ıstico da Figura 2.
q0
0
��
1 // q1 0 //
1
 
q2
0
��
1 // qf
0,1
q3
1
KK
0
>>
Figura 2. Autoˆmato finito determin´ıstico a ser minimizado
Resposta: O autoˆmato da Figura 2 atende aos 3 pre´-requisitos para aplicac¸a˜o do algoritmo de
minimizac¸a˜o:
– E´ AFD.
– Todos seus estados sa˜o alcanc¸a´veis a partir de q0.
– δ e´ total.
(a) Construc¸a˜o da tabela e marcac¸a˜o dos estados trivialmente na˜o-equivalentes:
q1 ×
q2 ×
q3 × ×
qf × ×
q0 q1 q2 q3
(b) Marcac¸a˜o os estados na˜o-equivalentes:
– Ana´lise do par (q0, q2) para o s´ımbolo 0: δ(q0, 0) = q0, δ(q2, 0) = q2, (q0, q2) na˜o deve ser
marcado.
– Ana´lise do par (q0, q2) para o s´ımbolo 1: δ(q0, 1) = q1, δ(q2, 1) = qf , (q0, q2) deve ser
marcado.
– Ana´lise do par (q0, qf ) para o s´ımbolo 0: δ(q0, 0) = q0, δ(qf , 0) = qf , (q0, qf ) na˜o deve ser
marcado.
– Ana´lise do par (q0, qf ) para o s´ımbolo 1: δ(q0, 1) = q1, δ(qf , 1) = qf , (q0, qf ) deve ser
marcado.
– Ana´lise do par (q1, q3) para o s´ımbolo 0: δ(q1, 0) = q2, δ(q3, 0) = q2, (q1, q3) na˜o deve ser
marcado.
– Ana´lise do par (q1, q3) para o s´ımbolo 1: δ(q1, 1) = q3, δ(q3, 1) = q3, (q1, q3) na˜o deve ser
marcado.
2
– Ana´lise do par (q2, qf ) para o s´ımbolo 0: δ(q2, 0) = q2, δ(qf , 0) = qf , (q2, qf ) na˜o e´
marcado. (Um par na˜o e´ inserido na sua pro´pria lista.)
– Ana´lise do par (q2, qf ) para o s´ımbolo 1: δ(q2, 1) = qf , δ(qf , 1) = qf , (q2, qf ) na˜o deve
ser marcado.
Este passo produz a tabela a seguir:
q1 ×
q2 × ×
q3 × ×
qf × × ×
q0 q1 q2 q3
(c) Unificac¸a˜o dos estados equivalentes o produz o autoˆmato m´ınimo a seguir:
q0
0
��
1 // q1/q3
1
��
0 // q2/qf
0,1
��
3