A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 11 de 49

∪ {q3}) = E({q3, q4} = {q3, q4}.
δ({q2, q3}, 1) = E(∪q∈{q2,q3}∆(q, 1)) = E(∆(q2, 1) ∪∆(q3, 1)) =
= E(∅ ∪ {q2}) = E({q2}) = {q2}.
δ({q3}, 0) = E(∪q∈{q3}∆(q, 0)) = E(∆(q3, 0)) = E({q3}) = {q3}.
δ({q3}, 1) = E(∪q∈{q3}∆(q, 1)) = E(∆(q3, 1)) = E({q2}) = {q2}.
Surgiram dois novos estados após o cálculo destas transições: {q3, q4} e {q2}.
Adicionamos estes estados à tabela e continuamos os cálculos para estes novos
estados.
δ 0 1
{q1} {q2, q3} {q3}
{q2, q3} {q3, q4} {q2}
{q3} {q3} {q2}
{q3, q4}
{q2}
Continuamos os cálculos desta forma até que não surjam novos estados no cálculo
das transições. A tabela completa da função δ ficará da seguinte forma:
δ 0 1
{q1} {q2, q3} {q3}
{q2, q3} {q3, q4} {q2}
{q3} {q3} {q2}
{q3, q4} {q1, q2, q3} {q2, q3, q4}
{q2} {q3, q4} ∅
{q1, q2, q3} {q2, q3, q4} {q2, q3}
{q2, q3, q4} {q1, q2, q3, q4} {q2, q3, q4}
∅ ∅ ∅
{q1, q2, q3, q4} {q1, q2, q3, q4} {q2, q3, q4}
Como o único estado final do AFND original era q4, os estados finais do nosso
AFD são {q3, q4}, {q2, q3, q4} e {q1, q2, q3, q4}.
3. EXERCÍCIOS 59
EXEMPLO 4.16.
I // WVUTPQRSq1
0
,,
1
��
WVUTPQRSq2
0
ll
0
��
1
\\
WVUTPQRSq3
0
RR
1
//
1
>>⑦⑦⑦⑦⑦⑦⑦⑦⑦⑦⑦⑦⑦ WVUTPQRSONMLHIJKq4
1
ll
ε
RR
Considere o AFND descrito acima. Vamos calcular o AFD equivalente a ele. Co-
meçamos calculando qd0 = E({q0}) = E({q1}) = {q1}. Agora calculamos incre-
mentalmente a tabela de transição δ.
δ 0 1
{q1} {q2} {q3}
{q2} {q1, q2, q4} {q2}
{q3} {q1} {q2, q4}
{q1, q2, q4} {q1, q2, q4} {q2, q3}
{q2, q4} {q1, q2, q4} {q2, q3}
{q2, q3} {q1, q2, q4} {q2, q4}
Como o único estado final do AFND original era q4, os estados finais do nosso
AFD são {q1, q2, q4} e {q2, q4}. Repare também que, com a abordagem incremen-
tal, não precisamos construir os 16 estados de P(Q). A construção de 6 estados
foi suficiente.
3. Exercícios
(1) Desenhe o diagrama de estados de cada um dos seguintes autômatos fini-
tos não determinísticos e construa o autômato finito determinístico equi-
valente a cada um deles. Em cada caso o estado inicial é q1.
a) F1 = {q4} e a função de transição é dada por:
60 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
∆1 a b c
q1 {q1, q2, q3} ∅ ∅
q2 ∅ {q4} ∅
q3 ∅ ∅ {q4}
q4 ∅ ∅ ∅
b) ∆2 = ∆1 e F2 = {q1, q2, q3}.
c) F3 = {q2} e a função de transição é dada por:
∆3 a b
q1 {q2} ∅
q2 ∅ {q1, q3}
q3 {q1, q3} ∅
(2) Seja A um autômato finito determinístico com um único estado final.
Considere o autômato finito não determinístico A′ obtido invertendo os
papéis dos estados inicial e final e invertendo também a direção de cada
seta no diagrama de estado. Descreva L(A′) em termos de L(A).
(3) Mostre que todo AFND pode ser convertido em outro equivalente que
possui apenas um único estado final.
CAPíTULO 5
Operações com Autômatos Finitos e Linguagens Regulares
No capítulo 3 vimos como obter a expressão regular da linguagem aceita por
um autômato finito. Neste capítulo, iremos resolver o problema inverso; isto é,
dada uma expressão regular r em um alfabeto Σ, construímos um autômato finito
que aceitaL(r). Na verdade, o autômato que resultará de nossa construção não será
determinístico. Mas isto não é um problema, já que sabemos como convertê-lo em
um autômato determinístico usando a construção de subconjuntos.
Na segunda parte deste capítulo, iremos analisar as chamadas propriedades de
fechamento das linguagens regulares com relação às seis operações de linguagens
que definimos: união, concatenação, estrela de Kleene, interseção, complemento e
diferença.
1. Considerações Gerais
Seja r uma expressão regular no alfabeto Σ. Nossa estratégia consistirá em
utilizar a expressão regular r como uma receita para a construção de um autômato
finito não determinístico M(r) que aceita L(r). Entretanto, como vimos no capí-
tulo 2, r é definida, de maneira recursiva, a partir dos símbolos de Σ, ε e ∅, por
aplicação sucessiva das operações de união, concatenação e estrela. Por isso, efe-
tuaremos a construção de M(r) passo a passo, a partir dos autômatos que aceitam
os símbolos de Σ, ε e ∅.
Contudo, para que isto seja possível, precisamos antes resolver alguns pro-
blemas. O primeiro, e mais simples, consiste em construir autômatos finitos que
aceitem um símbolo de Σ, ou ε ou ∅. Estes autômatos funcionarão como os áto-
mos da construção. Os problemas mais interessantes dizem respeito à construção
de novos autômatos a partir de autômatos já existentes. Suponhamos, então, que
M1 e M2 são autômatos finitos não determinísticos. Precisamos saber construir
61
62 5. OPERAÇÕES COM AUTÔMATOS FINITOS E LINGUAGENS REGULARES
(1) um autômato Mu que aceita L(M1) ∪ L(M2);
(2) um autômato Mc que aceita L(M1) · L(M2); e
(3) um autômato M1∗ que aceita L(M1)∗.
Se formos capazes de inventar maneiras de construir todos estes autômatos, então
seremos capazes de reproduzir a montagem de r passo a passo no domínio dos
autômatos finitos, o que nos levará a um autômato finito que aceita L(r), como
desejamos.
Começaremos descrevendo os átomos desta construção; isto é, os autômatos
que aceitam símbolos de Σ, ε e ∅. Seja σ ∈ Σ. Um autômato simples que aceita σ
é dado pelo grafo
I // WVUTPQRSq1 σ // WVUTPQRSONMLHIJKq2
O autômato que aceita ε é ainda mais simples
I // WVUTPQRSONMLHIJKq1
Para obter o que aceita ∅ basta não declarar nenhum estado como sendo final. A
maneira mais simples de fazer isto é alterar o autômato acima, como segue.
I // WVUTPQRSq1
Construídos os átomos, falta-nos determinar como podem ser conectados para ob-
ter estruturas maiores e mais complicadas. Passamos, assim, à solução dos proble-
mas enunciados acima.
2. União
Suponhamos que M e M′ são autômatos finitos não determinísticos em um
mesmo alfabeto Σ. Mais precisamente, digamos que
(2.1) M = (Σ, Q, q0, F,∆) e M′ = (Σ, Q′, q′0, F ′,∆′).
2. UNIÃO 63
Assumiremos, também, que Q∩Q′ = ∅. Observe que esta hipótese não representa
nenhuma restrição expressiva, já que para alcançá-la basta renomear os estados de
M′, no caso de serem denotados pelo mesmo nome que os estados de M.
Um outro detalhe que vale a pena mencionar é que, tanto nesta construção,
como na da concatenação, estamos supondo que ambos os autômatos estão defi-
nidos para um mesmo alfabeto. Novamente, esta restrição é apenas aparente já
que os autômatos não precisam ser determinísticos. De fato, podemos aumentar o
alfabeto de entrada de um autômato não determinístico o quanto quisermos, sem
alterar o seu comportamento. Para isso basta decretar que as transições pelos no-
vos símbolos são todas vazias. No caso da união, isto significa que, se M e M′
tiverem alfabetos de entrada Σ e Σ′ diferentes, então podemos considerar ambos
como autômatos no alfabeto Σ ∪ Σ′. Para mais detalhes veja o exercício 1.
Vejamos como deve ser o comportamento de um autômato finito Mu para que
aceite L(M) ∪ L(M′). O autômato Mu aceitará uma palavra w ∈ Σ∗ somente
quando w for aceita por M ou por M′. Mas, para descobrir isto, Mu deve ser
capaz de simular estes dois autômatos. Como estamos partindo do princípio de
que Mu é não determinístico, podemos deixá-lo escolher qual dos dois autômatos
vai querer simular em uma dada computação. Portanto, ao receber uma palavra w,
o autômato Mu:
• escolhe se vai simular M ou M′;
• executa a simulação escolhida e aceita w apenas se for aceita pelo autô-
mato cuja simulação está sendo executada.
Uma maneira de realizar isto em um autômato finito é criar um novo estado inicial
q̂0 cuja única função é realizar a escolha de qual dos dois autômatos será simulado.
Mais uma vez, como Mu não é determinístico, podemos deixá-lo decidir, por si
próprio, qual o autômato que será simulado. Para isto, basta acrescentarmos uma
ε-transição

Crie agora seu perfil grátis para visualizar sem restrições.