(Parte 1 de 7)

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-1

Linguagens Formais

Capítulo 4: Autômatos finitos e expressões regulares

– com Luiz Carlos Castro Guedes

4.1 - Introdução

Neste capítulo estudaremos uma máquina (um procedimento aceitador, ou reconhecedor), chamada autômato finito (af). A palavra finito é incluída no nome para ressaltar que um af só pode conter uma quantidade finita e limitada de informação, a qualquer momento. Essa informação é representada por um estado da máquina, e só existe um número finito de estados.

Essa restrição faz com que o af seja severamente limitado na classe de linguagens que pode reconhecer, composta apenas pelas linguagens regulares, como mostraremos neste capítulo.

Duas versões do af são estudadas aqui: o af determinístico (afd) e o af não determinístico (afnd). Este capítulo mostra que uma linguagem regular pode ser definida de quatro formas:

·através de uma gramática regular (definição); •através de um afd que reconhece a linguagem;

•idem, através de um afnd;

•através de uma expressão regular, um mecanismo a ser introduzido com essa expressa finalidade.

4.2 - Autômato finito determinístico

Como observado acima, a informação que um af guarda sobre a entrada (mais precisamente sobre a parte da entrada já lida) é representada por um estado, escolhido em um conjunto finito de estados. A definição formal de automato finito, na sua versão determinística é dada a seguir.

Definição. Um Autômato Finito Determinístico (afd) M, sobre um alfabeto S é um sistema (K, S, d, i, F), onde K é um conjunto de estados finito, não vazio;

S é um alfabeto de entrada (finito) d: K·S fi K é a função de transição iK é o estado inicial FK é o conjunto de estados finais.

O nome determinístico faz referência ao fato de que d é uma função (também chamada função próximo-estado), que determina precisamente o próximo estado a ser assumido quando a máquina M se encontra no estado q e lê da entrada o símbolo a: o estado d(q, a).

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-2

De forma simplificada, podemos dizer que um afd aceita uma cadeia se, partindo do estado inicial, e mudando de estado de acordo com a função de transição, o afd atinge um estado final ao terminar de ler a cadeia. Uma das maneiras de visualizar o funcionamento de um afd é através de um controle finito que lê símbolos de uma fita de entrada (onde se encontra a cadeia de entrada), sequencialmente, da esquerda para a direita. Os elementos do conjunto de estados K representam os estados possíveis do controle finito. A operação se inicia no estado inicial i, lendo o primeiro símbolo da fita de entrada. Por conveniência, considera-se que a cabeça de leitura se move sobre a fita, ao contrário do que seria de se esperar.

A Figura 4.1 representa um afd cujo controle está no estado q, e que está lendo o quarto símbolo da cadeia de entrada, um b.

Fig. 4.1 - Autômato Finito

Exemplo 1: Considere o afd M = (K, S, d, i, F), onde temos

K = { q0, q1, q2, q3 }

S = { a, b } i = q0 F = { q3 } e onde a função de transição d: { q0, q1, q2, q3 } · { a, b } fi { q0, q1, q2, q3 } é dada pela tabela abaixo d a b q0 q1 q2 q1 q0 q3 q2 q3 q0 q3 q2 q1

Alternativamente, podemos representar o afd M por um diagrama de transições, ou diagrama de estados, como o da Fig. 4.2. Note que o diagrama de transições determina completamente o automato M, através de algumas convenções:

•os estados são os nós do grafo, ou seja, K = { q0, q1, q2, q3 }; •o estado inicial é indicado pela seta, ou seja, i = q0;

•os estado finais são indicados pelo círculo duplo: q3 é o único estado final, ou seja, F = { q3 };

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-3

·as transições são as indicadas pelas arestas: d(q0, a) = q1, d(q0, b) = q2, d(q1, a) = q0, etc, ou seja, d é a mesma função representada pela tabela acima.

Cada estado de um af corresponde a uma determinada informação sobre a parte da cadeia de entrada já lida. No caso do exemplo, a informação pode ser descrita em frases curtas, mas isso nem sempre acontece. Para o estado q2, por exemplo, podemos dizer

"se o estado atingido é q2, o número de símbolos a já lidos é par, e o número de símbolos b já lidos é ímpar".

(Note que 0 é par.)

Fig. 4.2 - afd para o Exemplo 1

Em resumo, temos:

número de a'snúmero de b's q0 par par q1 ímpar par q2 par ímpar q3 ímpar ímpar

A linguagem aceita ou reconhecida por M (ver definição abaixo) é a linguagem formada pelas cadeias em que os números de a's e de b's são ambos ímpares. Isso se deve ao fato de que o único estado final é q3.

Por exemplo, a cadeia abaa é da linguagem de M, porque, com essa cadeia, os seguintes estados são atingidos: q0, q1, q3, q2, q3. Como o último estado é final, a cadeia é aceita.

A linguagem de um afd. Para definir a linguagem L(M), a linguagem das cadeias aceitas ou reconhecidas pelo afd M, podemos definir inicialmente uma configuração de M como sendo um par (q, x) K · S*, composto pelo estado corrente (o estado atual da máquina) e pela cadeia x, a parte da entrada que ainda não foi lida. Como observado, o

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-4 estado representa a parte já lida da cadeia de entrada. A configuração (i, x) é a configuração inicial de M para a cadeia x; qualquer configuração (q, e) é uma configuração final se q F. A mudança de configuração é caracterizada pela relação |—, definida abaixo:

(q, ax) |— (p, x) se e somente se d(q, a) = p ou seja, se tivermos d(q, a) = p, e se M estiver no estado q, lendo um símbolo a da cadeia de entrada, M moverá a cabeça de leitura uma posição para a direita e irá para o estado p. O símbolo a, depois de lido, não precisa mais aparecer na configuração. Podemos agora definir a linguagem L(M) por

Como em casos anteriores, |—* indica o fechamento reflexivo-transitivo da relação, no caso a relação |— de mudança de configuração, indicando que a configuração final pode ser atingida em zero ou mais passos.

Exemplo 1: (continuação) Para mostrar que abaa L(M), basta observar que

(q0, aba) |— (q1, ba) |— (q3, a) |— (q2, a) |— (q3, e), porque q3 é final. Por outro lado, como

(q0, abab) |— (q1,bab) |— (q3, ab) |— (q2, b) |— (q0, e), abab não pertence a L(M).

Uma caracterização alternativa de L(M) pode ser baseada em uma extensão $d da função d, feita de forma a aceitar cadeias no segundo argumento, isto é com domínio

K · S* em vez de K · S. Pode-se definir a nova função $d: K · S* fi K por

Fato: A função $d é realmente uma extensão de d, isto é, sempre que d é definida, $d também é, e tem o mesmo valor. Ou seja, se q K e a S, $d(q, a) = d(q, a).

Dem. Exercício.

Fato: A função $d e a relação |— se relacionam por

J. L. Rangel, L. C. Guedes - Ling. Formais - 4-5

Exemplo 1: (continuação) Para mostrar que abaa Î L(M), basta ver que $d(q0, aba) = $d(q1, ba) = $d(q3, a) = $d(q2, a) = $d(q3, e) = q3 F

(Parte 1 de 7)

Comentários