Autômatos Finitos não deterministicos

UNIVERSIDADE FEDERAL DE PELOTAS

PROGRAMA DE PÓS-GRADUAÇÃO EM COMPUTAÇÃO

DISCIPLINA DE TEORIA DA COMPUTAÇÃO

PROFESSORA SIMONE COSTA

AUTÔMATOS FINITOS NÃO DETERMINÍSTICOS E

AUTÔMATOS FINITOS NÃO DETERMINÍSTICOS COM

MOVIMENTO VAZIO

LEONARDO CAMPOS SOARES

WAGNER ISHIZAKA PENNY

ABRIL, 2014.

PPGC-UFPel Teoria da Computação

Autômatos Finitos não determinísticos

1 INTRODUÇÃO

Uma máquina de estados finitos, ou autômato finito, é um sistema capaz de

receber entradas e produzir saídas discretas, podendo assumir um número

finito e pré-definido de estados, no qual cada estado possui somente as

informações necessárias para determinar qual o estado seguinte.

Os autômatos finitos são capazes de descrever as linguagens da classe

regular, e seu controle pode ser determinístico, no qual o autômato não pode

assumir mais de um estado em qualquer instante, ou não determinístico, no

qual o autômato pode estar em vários estados ao mesmo tempo, sendo este

uma generalização do determinismo. Uma linguagem é dita regular se um

autômato finito a reconhece.

O não determinismo não expande as linguagens que podem ser aceitas por

autômatos finitos determinísticos, mas em alguns casos é muito mais eficiente

para a descrição e compreensão da função do autômato. Na prática, um

autômato finito não determinístico permite que utilizemos linguagens de alto

nível na descrição de um problema e, tendo a capacidade de processar a

mesma classe de linguagens que os autômatos finitos determinísticos, pode

ser convertido para este tipo e então ser processado por um computador

convencional. Sendo uma característica não essencial dos autômatos finitos, o

não determinismo pode ser remodelado a qualquer momento para um AFD

para ser processado pela linguagem de baixo nível dos autômatos.

Para correto entendimento da teoria dos autômatos é necessária a

compreensão dos conceitos a seguir.

• Alfabeto: Conjunto não vazio e finito de símbolos, representado por ∑.

• Potência de um alfabeto: ∑k = conjunto de palavras de tamanho K

formadas a partir de ∑.

• String: Sequência finita de símbolos formada a partir de um alfabeto.

• Comprimento de uma string: número de posições para símbolos em

uma palavra. O comprimento da string w é |w|.

• Linguagem: conjunto de strings, os quais escolhem seus símbolos a

partir de um alfabeto único.

• Linguagem Regular: uma linguagem é dita regular se um autômato

finito a reconhece.



Além disso existem também outras definições importantes:

• Estado inicial: estado inicial do autômato, na representação por grafos é

indicado por uma seta sem origem;

• Estado de aceitação: é o estado final do autômato, na representação por

grafos é indicado por um círculo duplo (estados simples usam círculos

simples);

• Transição – passagem de um estado para outro, no grafo é

representada pela seta que interliga dois estados;

• Função de transição – função que define, a partir do estado atual e do

símbolo de entrada, para qual estado o sistema irá se deslocar.

Os autômatos finitos não determinísticos são especialmente mais simples de

especificar nos casos a seguir:

• Modelagem de algoritmos com seleção;

• Definição de linguagens compostas por conjuntos bastante diferentes.

Adequado para descrever de forma concisa linguagens complexas.

2 Autômatos Finitos não determinísticos

Autômato finito não determinístico (AFN ou AFND) é aquele que possui a

capacidade de estar em mais de um estado ao mesmo tempo. É como se o

autômato tivesse a capacidade de adivinhar informações a respeito da entrada.

Um exemplo disto é a busca por determinadas sequências de caracteres em

um longo string de texto, em que é útil “adivinhar” que se está no início de um

string destes.

De um modo informal podemos dizer que um AFN é um autômato que possui,

da mesma forma que os AFD, um conjunto finito de estados, um conjunto finito

de símbolos de entrada, um estado inicial e um conjunto de estados de

aceitação. Também possui uma função de transição, mas ao contrário dos AFD



que retornam apenas um estado, nos AFN pode retornar um conjunto de zero,

um ou mais estados.

O autômato finito não determinístico é uma generalização dos autômatos finitos

determinísticos, ou seja, toda linguagem que é reconhecida por um AFN

também pode ser reconhecida por um AFD. Dessa forma pode-se escrever um

AFN como um AFD, entretanto muitas vezes o AFD obtido possui uma

quantidade muito maior de estados que o sistema não determinístico, se Q é a

quantidade de estados do AFN, a quantidade de estados do AFD será Q’ = 2Q.

2.1 Definição formal de um AFN

Pode-se definir um autômato finito não determinístico de maneira formal como

uma quíntupla M (Q, ∑, δ, q0, F), onde:

– Q é um conjunto finito de estados,

– ∑ é um alfabeto,

– q0 ϵ Q é o estado inicial,

– F ⊆ Q é o conjunto de estados finais (aceitação),

– δ: Q x ∑ � P(Q) é a função de transição.

Além desta definição formal através da tupla de cinco elementos, um AFN pode

ser descrito ainda de duas formas:

- Diagrama de transições através de grafos: grafo definido de modo que

para estado exista apenas um nó correspondente; haja conexão entre nós

chamada de transição e definida pelo estado atual e pelo símbolo de entrada;

existe uma seta no estado inicial q0 identificada como Início, a qual não se

origina em nenhum outro nó; estados em estado de aceitação possuem círculo

duplo e em estado de não aceitação possuem círculo simples.

- Tabela de transições que tabula a função δ: representação

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

um conjunto de valores (AFN) ou um valor (AFD). As linhas da tabela

correspondem aos estados e as colunas correspondem às entradas.



Exemplo 1: Dado o AFN descrito pelo grafo a seguir, encontre a tabela de

transição de estados e resolva de forma que sejam aceitas apenas strings com

final 01, dada a sequência de entrada 00101.

De maneira formal este grafo pode ser representado por:

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

Onde a função δ é dada pela seguinte tabela de transições:

TABELA DE TRANSIÇÃO DE ESTADOS

0 1

� q0 {q0, q1} {q0}

q1 Ø {q2}

*q2 Ø Ø

Na tabela o estado inicial recebe uma seta e o estado de aceitação é marcado

com um asterisco. Quando não existe nenhuma transição de um dado estado

sobre um dado símbolo de entrada o resultado adequado é o conjunto vazio.

Para a sequência dada o autômato está no seu estado inicial. Ao ler a entrada

0 ele pode ir para dois estados: q0 e q1. Neste caso o autômato encontra-se

nos estados q0 e q1 ao mesmo tempo. A próxima entrada é 0, a partir de q1

não existe qualquer ação com entrada 0, então este ramo “morre” na análise.

Já o ramo em q0 vai para q0 e q1 novamente. A próxima entrada é 1, assim o

estado q1 vai para q2 e a entrada 001 é aceita e o estado do ramo q0 vai para

q0. Entretanto a entrada não está encerrada. A quarta entrada é 0, a partir de

q2 não existe qualquer ação com entrada 0, então este ramo “morre” na

análise. O ramo que estava em q0 vai para q0 e q1. A última entrada, um 1, faz

com que q1 vá para q2 e q0 vá para q0, dessa forma atinge-se novamente o

estado de aceitação e a entrada 00101 é aceita.



Nesta figura consta a maneira pela qual o AFN processa as entradas.

3 Autômato Finito não determinístico com movimento vazio

(AFND-ε)

Um autômato finito não determinístico com movimento vazio, ou com ԑ-

transições, é uma generalização dos AFND, que não expande a classe de

linguagens aceita por estes, mas que acrescenta uma desejável conveniência

de programação ao permitir a mudança de um estado para outro sem que seja

feita a leitura de um caractere da fita de entrada. Como generalização de um

AFND, pode ser simulado por este, e também por um AFD.

Um movimento vazio, ou ε-transição, consiste em uma mudança interna no

estado do autômato. A mudança ocorre sem a leitura de qualquer dado na fita

de entrada. A não ser por uma eventual mudança de estado, nenhuma outra

ação pode ser observada em um movimento vazio.

Os AFND-ε podem ser definidos da mesma forma que um AFND, mas a

função de transição deve acrescentar o {ԑ} para permitir as operações de

mudança de estado sobre a string vazia. Um autômato finito não-determinístico

com movimento vazio é uma quíntupla M=(Q, ∑, δ, q0, F) onde:

– Q é um conjunto finito de estados

– ∑ é um alfabeto,

– q0 ϵ Q é o estado inicial

– F ⊆ Q é o conjunto de estados finais

– δ é a função de transição δ: Q x ∑ԑ � P(Q), onde ∑ԑ = ∑ U {ԑ}

PPGC-UFPel

Autômatos Finitos não

Podemos representar um

estados ou através de um diagrama de estados. A tabela conterá linhas com os

estados possíveis de serem assumidos, e as colunas terão as entradas

possíveis, enquanto os diagramas terão

aceitação), representado

Teoria da Computação


Podemos representar um AFND-ε através de uma tabela de transição



possíveis, enquanto os diagramas terão estados inicial, intermediário

representados de forma distinta, e setas representam as transições.

Teoria da Computação

através de uma tabela de transição de



estados inicial, intermediário e final (de

s de forma distinta, e setas representam as transições.



- Função Fecho-ԑ (também conhecida como Fecho-Vazio e ECLOSE)

Pode ser definida informalmente como a função que recebe um estado q e

retorna o conjunto de estados composto por q e todos os estados em que é

possível chegar a partir de q seguindo transições rotuladas por ε.

Formalmente podemos definir Fecho-ε(q) recursivamente:

- O estado q está em Fecho-ε(q)

- Se o estado p está em Fecho-ε(q), e existe uma transição do estado p para o

estado r rotulada por ε, então r está em Fecho-ε(q).

Exemplo 2: Eliminação de transições vazias em um AFND-ε

Utilizando-se a tabela de transição de estados:

1. Elimine-se a coluna do δ, incluindo em cada estado que possui arco- ԑ o

destino do mesmo.

2. Incluem-se os demais estados, seguindo o mesmo procedimento.



1) A primeira etapa é a construção da tabela de transição de estados da

AFN, que está representada pela tabela da esquerda, chamaremos de φ

a função de transição da AFN e de δ a função de transição da AFD .

2) O segundo passo é a construção de uma tabela para representar as

transições da AFD através do produto cartesiano dos estados da AFD,

chama-se a cada produto destes estado S0, S1, ....Sn., incluindo como

último estado o conjunto vazio.

δ a b

S0={q0}

S1={q1}

S2={q0,q1}

S3={ }

Sempre existirá 2k combinações, onde k é o número de estados do AFN,

assim, na pior das hipóteses, o AFD possuirá no máximo 2k estados.

3) Mostrar todos os conjuntos que contêm como elemento estados finais

como novo estado final de δ, neste caso todos estados que contenham

q1, o qual é o estado de aceitação.



δ a b

S0={q0}

S1={q1}

S2={q0,q1}

S3={ }

Neste caso os estados que contêm q1 são os estados S1 e S2.

4) Verificar a ocorrência de cada conjunto de δ em relação a um símbolo e

colocar como resultado o conjunto correspondente que pertence a δ.

Quando existir mais de um elemento no conjunto a ocorrência passa a

ser a união das ocorrências de todas as transições.

δ a b

S0={q0} q0, q1 = S2 S3

S1={q1} S3 q1=S1

S2={q0,q1} q0, q1 = S2 q1=S1

S3={ } S3 S3

A interpretação desta etapa é a seguinte: se estou no estado q0 e q1 ao

mesmo tempo, e recebo “a” o estado q0 e q1 é mantido, se recebo “b” o

sistema passa a estar no estado q1. Caso não exista atividade com

determinada entrada para determinada situação a resposta é o conjunto

vazio, por exemplo no estado S0 se recebe “b” não existe atitude a ser

tomada pelo autômato, assim a resposta é o conjunto vazio.

5) Eliminar as linhas que possuem transições somente com saídas, ou

seja, não existe nenhuma transição que chega até ela (estado

inacessível). Neste caso não existe estado inacessível.

6) Montar o AFD a partir de δ.



7) Eliminar estados que não possuem saída para nenhum outro estado e

não são finais. Neste caso apenas o estado S3 será eliminado.



8) Verificar se uma cadeia qualquer, por exemplo “aab” pertence tanto ao

AFN quanto ao AFD.

No AFN teríamos que:

O estado final em um AFN para a cadeia “aab” é q1.

No AFD teríamos que:

O estado final em um AFD para a cadeira “aab” é S1, que é o mesmo

estado q1.

Logo a cadeia dada pertence tanto ao AFN quanto ao AFD gerado.



REFERÊNCIAS BIBLIOGRÁFICAS

HOPCROFT, John, ULLMAN, Feffrey, MOTWANI, Rajeev. Introdução à teoria

de autômatos, linguagens e computação. Editoral Elsevier, 2002.

LEWIS, Harry R., PAPADIMITRIOU, Christos. Elementos de teoria da

computação. Editora Bookman, 2008.

SIPSER, Michael. Introdução à teoria da computação. São Paulo: Thompson,

2007. 459p.

Documents

Autômatos Finitos não deterministicos