Automatos

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1527 palavras )
  • Download(s) : 0
  • Publicado : 8 de dezembro de 2012
Ler documento completo
Amostra do texto
FACENS - Faculdade de Engenharia de Sorocaba

T´picos em Computa¸ao I o c˜

Equivalˆncia entre AFD e AFN e
Autˆmato Finito N˜o-Determin´ o a ıstico (AFN)
estado anterior


Exemplo
L = {w | w ∈ (a |a+ b∗ ) } M = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 } F = {q0 , q1 }
a,b

q
a a a símbolo lido conjunto de novos estados

δ

a

b {q1 }

q0 {q0 , q1 } q1 -

p1

p2

...pn

A fun¸˜o programa, ao processar um entrada ca (estado corrente e s´ ımbolo lido), tem como resultado um conjunto de novos estados.

q0

a

q1

a

q2

a

q3

O n˜o determinismo ´ uma importante generaliza¸˜o dos a e ca modelos de m´quinas, sendo de fundamental importˆncia no esa a tudo da teoria da computa¸˜o e das linguagens formais. Qualquer ca AFN pode ser simulado porum AFD. Pode-se entender que o AFN assume simultaneamente todas as alternativas de estados poss´ ıveis {p0 , p1 , ..., pn } a partir do estado atual (q) e do s´ ımbolo lido (a).

• o ciclo em q0 realiza uma varredura pela entrada de s´ ımbolos a’s • o caminho q0 /q1 garante a ocorrˆncia de a antes da e ocorrˆncia de b’s e

AFN - Defini¸˜o ca
• M = (Σ, Q, δ, q0 , F ) – Σ – alfabeto de s´ımbolos de entrada – Q – conj. de estados poss´ ıveis do autˆmato o o qual ´ finito e – δ – fun¸˜o de transi¸˜o ca ca – q0 – estado inicial (q0 ∈ Q) – F – conjunto dos estados finais tal que F est´ contido em Q a

Exerc´ ıcio
L = {w | w possui aaa como sufixo} M = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , qf } F = {qf }

δ

a

b

q0 {q0 , q1 } {q0 } q1 q2 qf {q2 } {qf } -

A linguagemaceita por um autˆmato finito n˜o-determin´ o a ıstico M = (Σ, Q, δ, q0 , F ) denotada por ACEITA(M), ou L(M) ´ o e conjunto de todas as palavras pertencentes a Σ∗ tais que existe pelo menos um caminho alternativo que aceita a palavra. Analogamente, REJEITA(M) ´ o conjunto de todas as e palavras pertencentes a Σ∗ rejeitadas por todos os caminhos alternativos de M (a partir de q0 ).

a,b

q0

aq1

a

q2

a

qf

Profa. Tiemi Christine Sakata

1

FACENS - Faculdade de Engenharia de Sorocaba

T´picos em Computa¸ao I o c˜

Exerc´ ıcios
Desenvolver AFNs que reconhe¸am as seguintes c linguagens sobre Σ = {a, b} 1. L1 = {w | o prefixo de w ´ aa} e 2. L2 = {w | w possui aa ou bb como subpalavra} 3. L3 = {w | w possui um n´mero par de a e b} u 4. L4 = {w|w possui um n´mero´ u ımpar de a}

3. M3 = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 } F = {q0 } δ q0 q1 q2 q3 q4 q5 q6 q7 q8 a {q1 , q3 } {q0 } {q0 } {q5 } {q4 } {q7 } {q6 } {q0 } b {q2 , q6 } {q0 } {q4 } {q3 } {q0 } {q0 } {q8 } {q7 }

a
Poss´ ıveis solu¸oes: c˜ 1. M1 = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , q3 } F = {q2 , q3 } δ q0 q1 q2 q3 a {q1 } {q2 } {q2 ,q3 } b {q2 , q3 } -

q6

a b b

q7

q2 b b

b

b a

q8

a a q1 a

q0 b a q5 a a q3 b b q4

a,b

q0

a

q1

a

q2

a,b

q3

2. M2 = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , qf } F = {qf } δ q0 q1 q2 qf a b {q0 , q1 } {q0 , q2 } {qf } {qf } {qf } {qf }

4. M4 = (Σ, Q, δ, q0 , F ) Σ = {a, b} Q = {q0 , q1 , q2 , q3 } F = {q1 , q2 } δ q0 q1 q2 qf a {q1 ,q2 } {q3 } {q2 } b {q0 } {q1 } {q2 } {q3 }

b
a,b

b

q0 a q1 b

q0

a

q1

b
q2

b a

a q2 q3 a

a qf

b a,b

Profa. Tiemi Christine Sakata

2

FACENS - Faculdade de Engenharia de Sorocaba

T´picos em Computa¸ao I o c˜

Equivalˆncia entre AFD e AFN e
• Um autˆmato finito n˜o-determin´ o a ıstico pode se transformar em um autˆmato finito o determin´ ısticoequivalente. • Dois autˆmatos s˜o considerados equivalentes o a se aceitam a mesma linguagem.

ϕ a b q0 {q1, q2} q1 {q2} {q0, q2} q2 {q2} {q0}
2. Construir a tabela de transi¸oes do AFD (δ) atrav´s do c˜ e produto cartesiano dos estados de ϕ, incluindo como ultimo ´ conjunto o vazio:

Embora a facilidade de n˜o-determinismo seja, aparentea mente, um significativo acr´scimo ao Autˆmato Finito, na...
tracking img