13/06/2010

1

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

cicero@engcomp.uema.br

Ca

pít

ulo

2

Au

tôm

ato

s fi

nit

os

de

term

inís

tico

s

Autômatos finitos determinísticos

� Autômato finito determinístico é aquele que se encontra em um

único estado depois de ler uma seqüência qualquer de entradas.

- o termo “determinístico” se refere ao fato de que, para cada

entrada, existe um e somente um estado ao qual o autômato pode

transitar a partir de seu estado atual. Em contraste, autômatos finitos

“não-determinísticos”, podem estar em vários estados ao mesmo

tempo.

- a expressão “autômato finito” irá se referir à

variedade determinística, embora utilizemos “determinístico” ou

abreviatura DFA (Deterministic Finite Automaton) normalmente, para

lembrar ao estudante o tipo de autômato mencionado.

2

Definição de um autômato finito determinístico

Um autômato finito determinístico consiste em:

1. Um conjunto finito de estados, freqüentemente denotado por Q.

2. Um conjunto finito de símbolos de entrada, freqüentemente

denotado por ∑.

3. Uma função de transição que toma como argumentos um estado

e um símbolo de entrada e retorna um estado. A função de

transição será comumente denotada por δ. Em nossa

representação gráfica informal de autômatos, δ foi representada

pelos arcos entre estados e pelos rótulos nos arcos. Se q é um

estado, e a é um símbolo de entrada, então δ(q, a) é o estado p

tal que existe um arco identificado por a de q até p.1

3

1 Mais precisamente, o grafo é uma representação de alguma função de transição δ, e os

arcos do grafo são construídos para refletir as transições especificadas por δ.

13/06/2010

2

4

Definição de um autômato finito determinístico

Cont...

4. Um estado inicial, um dos estados em Q.

5. Um conjunto de estados finais ou de aceitação F. O conjunto F é

um subconjunto de Q.

Um autômato finito determinístico será com freqüência referido

pelo seu acrônimo: DFA. A representação mais sucinta de um DFA

é uma listagem dos cinco componentes anteriores. Em provas,

mencionaremos com freqüência um DFA pela notação “de uma

tupla de cinco elementos”:

A = (Q, ∑∑∑∑, δδδδ, q0, F)

Onde A é o nome do DFA, Q é seu conjunto de estados, ∑ é seu conjunto de símbolos de

entrada, δ sua função de transição, q0 é seu estado inicial e F é seu conjunto de estados

de aceitação. 4

55

Como um DFA processa strings

1. O primeiro detalhe que precisamos entender sobre um DFA é

como o DFA decide se deve ou não “aceitar” uma seqüência de

símbolos de entrada.

2. A “linguagem” do DFA é o conjunto de todos os strings que o DFA

aceita.

3. Suponha que a1a2 ... an seja uma seqüência de símbolos de

entrada.

4. Começamos com o DFA em seu estado inicial, q0.

5. Consultamos a função de transição δδδδ, digamos δ(q0, a1) = q1, para

encontrar o estado em que o DFA A entra depois de processar o

primeiro símbolo de entrada a1.

5

666

Como um DFA processa strings – cont...

6. Processamos o próximo símbolo de entrada, a2, avaliando δ(q1, a2);

vamos supor que esse estado seja q2. Continuamos dessa maneira,

encontrando os estados q3, q4, ..., qn tais que δ(qi-1, ai) = qi para cada

i.

7. Se qn é um elemento de F, então a entrada a1a2 ... an é aceita e, se

não, ela é “rejeitada”.

� Veja o exemplo 2.1 (Hopcroft, p. 49-50) como um DFA

processa uma string:

6

13/06/2010

3

7

Exemplo 2.1: Vamos especificar formalmente um DFA que aceita todos

e somente os strings 0´s e 1´s que a sequência 01 em algum lugar no

string. Podemos escrever essa linguagem L como:

{w | w é da forma x01y para alguns strings x e y que consistem somente

em 0´s e 1´s}

Outra descrição equivalente, usando parâmetros x e y à esquerda da

barra vertical, é:

{x01y | x e y são quaisquer strings de 0´s e 1´s}

Os exemplos de strings na linguagem incluem 01, 11010 e 100011. Os

exemplos de strings que não estão na linguagem incluem ε, 0 e 111000.

8

O que sabemos sobre um autômato que pode aceitar essa linguagem

L?� seu alfabeto de entrada é ∑ = {0,1}

� ele tem algum conjunto de estados, Q, dos quais um estado,

digamos q0, é o estado inicial.� o autômato tem de memorizar os fatos importantes sobre a

parte da entrada que viu até o momento.

� Para decidir se 01 é um substring da entrada, A precisa lembrar:

1. Ela já viu 01? Nesse caso, ele aceita toda sequência de

entradas adicionais; isto é, ele só estará em estados de

aceitação de agora em diante.

2. Ele nunca viu 01, mas sua entrada mais recente foi 0; assim,

se agora ele vir o 1, terá visto 01 e poderá aceitar tudo que vir

daqui por diante?

3. Ele nunca viu 01, mas sua última entrada ou foi não-existente

(ele apenas iniciou), ou viu um 1? Nesse caso, A não pode

aceitar até ver primeiro um 0 seguido de um 1.

9

� Cada uma dessas três condições pode ser representada por um

estado. A condição (3) é representada pelo estado inicial, q0.

Certamente, quando apenas iniciamos, precisamos ver um 0 seguido de

um 1. Contudo, se no estado q0 vemos em seguida um 1, então não

estamos mais próximos de ver 01, e assim devemos ficar no estado q0.

Isto é, δ(q0, 1) = q0.

� No entanto, se estamos no estado q0 e em seguida vemos um 0,

estamos na condição (2). Isto é, nunca vimos 01, mas temos nosso 0.

Desse modo, vamos usar q2 para representar a condição (2). Nossa

transição de q0 sobre a entrada 0 é δ(q0, 0) = q2.

� Agora, vamos considerar as transições a partir do estado q2. Se vemos

um 0, não estamos em situação melhor do que antes, mas ela também

não é pior. Não vimos 01, mas 0 foi o último símbolo, e assim ainda

estamos esperando por um 1. O estado q2 descreve essa situação

perfeitamente, e então queremos δ(q2, 1) = q1.

13/06/2010

4

10

� Finalmente, devemos projetar as transições sobre o estado q1. Nesse

estado, já vimos uma sequência 01; então, independente do que

acontecer, ainda estaremos em uma situação na qual vimos 01. Isto é,

δ(q1, 0) = δ(q1, 1) = q1.

� Dessa forma, Q = {q0, q1, q2}. Como dissemos, q0 é o estado inicial, e o

único estado de aceitação é q1; isto é, F = {q1}. A especificação

completa do autômato A que aceita a linguagem L de strings que têm

como substring 01, é:

A = ({q0, q1, q2}, {0,1}, δ, q0, {q1})

onde δ é a função de transição descrita anteriormente.