17/06/2010

1

Teoria da ComputaçãoProf. Cícero Costa Quarto

ccquarto@gmail.com

Ca

pít

ulo

2

Au

tôm

ato

s fi

nit

os

de

term

inís

tico

s

Notações mais simples para DFA´s

Especificar um DFA como uma tupla de cinco elementos, com uma

descrição detalhada da função de transição δ, é ao mesmo tempo

tedioso e difícil de ler. Há duas notações preferenciais para descrever

autômatos:

� Um diagrama de transições, que é um grafo (cf. Fig. 1a)

� Uma tabela de transições, que é uma listagem tabular da

função (cf. Fig. 1b)

2

0

q0

Símbolos de entrada

Est

ados

(a)

(b)

Fig. 1: Notações de representação de DFA´s

Diagrama de transições

Um diagrama de transições para um DFA A = {Q, ∑, δ, q0, F) é um

grafo definido como a seguir:

a) Para cada estado em Q existe um nó correspondente

b) Para cada estado q em Q e para cada símbolo de entrada a em

∑, seja δ(q, a) = p. Então, o diagrama de transições tem um arco do

nó q para o nó p, rotulado por a. Se existirem vários símbolos de

entrada que causam transições de q para p, então o diagrama de

transições pode ter um arco rotulado pela lista desses símbolos.

c) Existe uma seta no estado inicial q0, identificada como Início.

essa seta não se origina em nenhum nó.

d) Os nós correspondentes aos estados de aceitação (aqueles em

F) são marcados por um círculo duplo. Estados que não estão em F

têm um único círculo.

3

17/06/2010

2

4

Exemplo 2.2: A Figura 2.4 mostra o diagrama de transições para o DFA

que aceita todos e somente os strings de 0´s e 1´s que têm a sequência

01 em algum lugar no string.

q0

1

0q2

0

1q1

0,1

Início

Figura 2.4: O diagrama de transições para o DFA que

aceita todos os strings que contém o substring 01

� Vemos nesse diagrama os três

nós que correspondem aos três

estados. Há uma seta Início

entrando no estado inicial, q0, e o

único estado de aceitação, q1, é

representado por um círculo duplo.

� Fora de cada estado há um arco

rotulado por 0 e um arco rotulado

por 1 (embora os dois arcos estejam

combinados em um só com um

rótulo duplo no caso de q1).� Cada um dos arcos corresponde a

um dos valores de δ desenvolvidos

no autômato que aceita todos e

somente os strings de 0´s e 1´s que

têm a sequência 01 em algum lugar

no string.

Tabela de transições

� Uma tabela de transições é uma representação convencional e

tabular de uma função como δ que recebe dois argumentos e retorna

um valor.

���� As linhas da tabela correspondem aos estados, e as colunas correspondem

às entradas.

���� A entrada para a linha correspondente ao estado q e para a coluna

correspondente à entrada a é o estado δ(q, a).

Exemplo 2.3: A tabela de transições correspondente à função δ do autômato que

aceita

todos os strings que contêm o substring 01 é mostrada na Fig. 2.5. Também é

mostrada na

tabela duas outras características de uma tabela de transições:

���� O estado inicial é marcado com uma seta;

���� Os estados de aceitação estão marcados com um asterisco

5

6

0 1

→ q0 q2 q0

*q1 q1 q1

q2 q2 q1

Figura 2.5: Tabela de transições

para o DFA que aceita todos os

strings que contêm o substring

01.

Como podemos deduzir os conjuntos

de estados e os símbolos de entrada

examinando os nomes das linhas e

colunas, podemos ler na tabela de

transições todas as informações de

que precisamos para especificar o

autômato finito de modo único.