Aula 04 – Teoria da Computação

Autômatos finitos

No link você pode baixar a apresentação usada em sala de aula. Não estude apenas pela apresentação.

A partir de agora vamos estudar as máquinas que conseguem ler as linguagens que aprendemos anteriormente.

Introdução

Vimos anteriormente que o problema geral da análise sintática é muito difícil. Felizmente, em alguns casos particulares ele se torna mais simples. Nesta seção, vamos estudar um destes casos. Vamos tomar como exemplo a seguinte gramática G:

• S→0A|1S
• A→0S|1A|ε 

A notação acima equivale a:

• S→0A
• S→1S
• A→0S
• A→1A
• A→ε

Por questão de economia de espaço na página usaremos a primeira notação.

Esta gramática gera as cadeias sobre o alfabeto Σ={0, 1} , que têm quantidade ímpar de caracteres ‘0’. Por exemplo, esta gramática gera a cadeia 01010 da seguinte forma:

S⇒0A⇒01A⇒010S⇒0101S⇒01010A⇒01010

Programar a análise sintática é resolver o problema oposto. Dada a cadeia 01010, podemos determinar se ela está na linguagem gerada pela gramática? Para programar a solução podemos guardar sempre qual é o único não terminal que está no final da cadeia sendo gerada. Se ao final o não terminal for ‘A’, como existe a regra A→ε, então a cadeia estará na linguagem. Esta solução pode ser representada pela ilustração abaixo:

Chamamos esta solução de AFD – Autômato Finito Determinístico. A ideia é que cada bola representa um ”estado”. Começamos pelo estado marcado com a seta, no caso, o estado ‘S’. Ao lermos um 0 vamos para o estado ‘A’; ao lermos um ‘1’, permanecemos no estado ‘A’. Depois, ao lermos o segundo ‘0’, voltamos ao estado ‘S’. Ao terminarmos de ler a cadeia de entrada, se estivermos em um estado marcado com círculo duplo, neste caso no estado ‘A’, dizemos que a cadeia foi ‘reconhecida’. Caso contrário, a cadeia não foi reconhecida pelo AFD (GARCIA, 2017).

Em um AFD, dado um estado e um símbolo do alfabeto de entrada, existe uma seta, ou transição para exatamente um único estado. Assim, o AFD está sempre em exatamente um estado, por isso é chamado de determinístico. Observamos que o AFD possui estados. No AFD da figura acima os estados são ‘S’ e ‘A’. O estado ‘S’ é o estado inicial (marcado com uma seta), no qual o AFD inicia sua execução. O estado ‘A’ é um estado final e se o autômato termina em um estado final (marcado com círculo duplo), ele reconheceu com sucesso a cadeia lida. Uma forma alternativa de representar este mesmo AFD é descrito na tabela abaixo:

 

	0	1
→S	A	S
*A	S	A

Tabela de uma Autômato Finito Determinístico.

Neste caso, o estado inicial é marcado com a seta. Os estados finais são marcados com o símbolo ‘*’ e, para sabermos para onde vai a seta do estado q com entrada a basta consultar a linha correspondente ao estado q e a coluna correspondente ao símbolo de entrada a . As setas – ou a tabela – representam uma função que, dado um estado e um símbolo da entrada, retorna um único estado.

Atenção

Formalmente um AFD é uma tupla (Q, Σ, δ, q₀, F), onde:

• Q é um conjunto finito e não vazio de estados.
• Σ é o alfabeto de entrada.
• δ : Q × Σ → Q é a função de transição de estados.
• q 0 ∈ Q é o estado inicial
• F ⊆ Q é o conjunto de estados finais.

No AFD da figura anterior temos que:

• Q=(S, A);
• Σ={0, 1};
• δ:Q×Σ→Q é a função na qual:
  • δ(S, 0)=A, δ(S, 1)=S, δ(A, 0)=S e δ(A, 1)=A
• S é o estado inicial;
• {A} é o conjunto de estados finais.

Para entendermos como o AFD funciona é útil estendermos a função δ: Q×Σ→Q para esta extensão, isto é, a função , representa a ação do AFD ao ler uma cadeia, ou seja, ao ler mais de um caractere. Sua definição é intuitiva: se ao lermos um 0 temos que δ(S, 0)=A, e o AFD fica no estado A. Ao lermos um segundo 0, temos δ(A, 0)=S e o AFD retorna ao estado S. Isso significa que =(S,00)=S. Formalmente podemos definir em função de δ da seguinte forma:

• (q , ε)=q, para todo q∈Q.
• (q, aw)=δ(δ (q, a),w), para todo q∈Q, a∈Σ, w∈Σ^*.

Aplicando esta definição ao AFD da Figura “Autômato Finito Determinístico”, com entrada 00, temos o seguinte:

• (S, 00)=(δ(S ,0), 0)=δ(A, 0)=(δ(A ,0),ε)=δ(S, ε)=S

Portanto, a definição funciona como esperávamos.

Finalmente estamos aptos a definir a linguagem gerada por um AFD M. Esta linguagem é formada por todas as cadeias reconhecidas por M, isto é, todas as cadeias que levam M a um estado final.

Dado um AFD M=(Q ,Σ ,δ, q₀ ,F) , definimos a linguagem reconhecida por M como:

• T(M)={w∈Σ^*(q₀, w)∈F}

AFND – Autômato Finito Não Determinístico

No caso do autômato da Figura “Autômato Finito Determinístico” temos que T(M)={0,01,10,011,101,110,000,011,…}, o conjunto de todas as cadeias com número ímpar de caracteres 0. Gostaríamos que o AFD fosse uma boa forma de resolver o problema da análise sintática para todas as linguagens regulares. Entretanto, não é claro como obter um AFD de algumas gramáticas regulares. Por exemplo, a gramática G₂ – descrita logo a seguir -, gera as cadeias sobre o alfabeto Σ = {0, 1} que possuem a subcadeia ’00’, isto é, que têm dois caracteres 0 seguidos. G₂ possui as regras:

• S→0S|1S|0A
• A→0B
• B→0B|1B|ε

Ao tentarmos transformar esta gramática em um autômato finito obtemos a figura abaixo:

Podemos dizer que nesta figura a função δ não retorna um estado, mas um conjunto de estados. Por exemplo, δ ( S , 0 ) = { S , A } , enquanto que δ ( A , 1 ) = ∅ , ambos os casos violam a condição de que para cada estado e símbolo de entrada as setas nos levem a exatamente um estado. Neste caso, dizemos que a figura representa um AFND – Autômato Finito Não Determinístico. O AFND da Figura “Autômato Finito não Determinístico” também pode ser representado em outra forma, como apresentado na tabela abaixo:

Podemos interpretar um AFND como podendo seguir diversos caminhos ao ler uma entrada. Se ao menos 1 dos caminhos levar o AFND a um estado final, dizemos que o AFND reconhece w.

Observe que a função δ neste caso não retorna um estado, mas sim um conjunto de estados, em particular pode ser o conjunto vazio. Assim a assinatura da função deve ser δ: Q×Σ→℘(Q).

O AFND da Figura “Autômato Finito não Determinístico” pode ser transformado em um AFD. Dissemos que um AFND pode seguir diversos caminhos ao ler uma entrada w. Vamos fazer um AFD que guarda os estados de todos esses possíveis caminhos. Como o AFND em questão tem apenas três estados, cada um dos possíveis caminhos seguidos ao lermos uma cadeia w estará em um desses três estados, portanto, os caminhos combinados poderão estar em nenhum estado, ou somente no estado {S}, ou em uma combinação de estados, por exemplo, {S, A, B}. Na pior das hipóteses há 2³=8 estados possíveis para esses caminhos combinados. Podemos assim desenhar o AFD da figura abaixo:

Conforme explicado, cada estado do AFD corresponde a todos os possíveis estados que o AFND estaria após ler determinada entrada. Em particular, o estado inicial é {S}, porque o AFND inicia apenas em S. Se δ² é a função de transição do AFD que desejamos obter, δ² ({S, A}, 0)=∪_{q∈{S ,A}}δ(q ,0)=δ(S ,0)∪δ(A ,0)={S, A}∪{B}={S ,A ,B}. Os estados finais do AFD correspondem aos conjuntos de estados do AFND que contém ao menos um estado final. No exemplo {S,A,B} e {S,B} são estados finais, porque contém o estado final B.

Dada uma gramática regular sabemos obter um AFND equivalente, a construção anterior nos mostra que dado um AFND podemos obter um AFD equivalente, portanto, para toda gramática regular G sabemos obter um AFD M equivalente, isto é, tal que T(M)=L(G). Isso significa que podemos fazer a análise sintática de forma eficiente para todas as linguagens regulares. Se fizermos um programa que simule um AFD, este consome tempo proporcional ao tamanho da entrada, pois para cada símbolo da cadeia de entrada o AFD precisa fazer um movimento entre dois estados. O consumo de memória, por sua vez, é constante e não depende do tamanho da entrada, basta armazenar a tabela de transição em uma matriz. Entretanto, no AFD obtido na Figura “AFD obtido a partir de um AFND”, é possível diminuir o número de estados sem afetar seu funcionamento. A figura abaixo exibe o mesmo AFD que a figura “AFD obtido a partir de um AFND”. Seus estados foram renomeados para a forma mais usual q₀, q₁ , … , e desenhamos uma linha tracejada para facilitar o entendimento da melhoria que pode ser feita no AFD.

Na figura acim há uma seta que ultrapassa a linha tracejada da esquerda para a direita, e não há seta no sentido oposto. Isto significa que uma vez ultrapassada a seta, não há “volta”, o que corresponde à especificação da linguagem, composta pelas cadeias sobre Σ={0, 1} que possuem a subcadeia ’00’. Uma vez que a subcadeia ’00’ ocorra na cadeia, qualquer continuação da cadeia terá esta característica.

Em um AFD, os estados q e r são equivalentes, se para toda entrada possível o AFD se comporta da mesma forma (reconhece as mesmas entradas) estando em q ou estando em r .

Dado um AFD M=(Q, Σ ,δ ,q₀ ,F) , e estados q, r∈Q, definimos que  q e r são equivalentes, ou q ≡ r , quando:

• ∀w∈Σ^*, δ(q ,w)∈F⇔δ(r ,w)∈F

Na figura “AFD com estados renomeados” é apresentado o caso que q 2 ≡ q 3 porque depois da linha tracejada qualquer entrada sempre leva a um estado final. Em geral, é mais fácil identificar estados que não são equivalentes do que estados que são equivalentes. Se fizermos a negação da definição de equivalência temos que:

• q≢r se, e somente se, ∃w∈Σ *, δ(q, w)∈F⇔δ(r, w)∉F

Esta condição pode ser dividida no caso em que w é a cadeia vazia e o caso onde w não é a cadeia vazia. Se w não é a cadeia vazia e q≢r, então w=aw₂, onde a∈Σ, e δ(q ,a)≢δ(r ,a), isso significa que a condição de não equivalência pode ser reescrita em dois casos, isto é, q≢r se um dos seguintes casos é verdadeiro:

1. q∈F⇔r∉F
2. ∃a∈Σ, δ(q, a)≢δ(r, a)

A partir disso podemos fazer um algoritmo de minimização que consiste em dois passos:

1. Marcar como não equivalente todo o par de estados (q, r) no qual q∈F⇔r∉F;
2. Percorrer todo o par de estados restante, marcando-o como não equivalente quando ∃a∈Σ, δ(q, a)≢δ(r ,a).

Veremos isso através de um exemplo. Considere o AFD da figura abaixo:

Vamos fazer uma matriz triangular conforme a tabela abaixo, onde cada par de estados é considerado uma única vez. Nesta matriz vamos marcar com um ‘X’ os pares de estados que atendem à primeira condição:q∈F⇔r∉F .

Após essa marcação falta analisar dois pares de estados: (q₀, q₃) e (q₁, q₂). Começaremos com (q₀, q₃) . Neste caso, temos que:

• δ(q0 ,0)=δ(q3 ,0)
• δ(q0, 1)=q1≢q3=δ(q3 ,1)

Devido ao movimento na segunda linha temos que ∃a∈Σ, δ(q₀, a)≢δ(q₃, a) portanto q₀≢q₃, podemos marcá-los na tabela “Segunda etapa da minimização do AFD”como não equivalentes:

Finalmente, devemos analisar o par (q₁, q₂₎. Neste caso, temos que:

• δ(q₁, 0)=δ(q₂, 0)
• δ(q₁, 1)=q₀≢q₃=δ(q₂, 1)

Mais uma vez, o movimento da segunda linha faz com que o par não seja equivalente. Portanto, abaixo fica toda marcada com ‘X’, o que significa que não há estados equivalentes, portanto, o AFD não pode ser melhorado.

É interessante voltarmos ao final da primeira fase, onde a situação era dada pela tabela “Primeira etapa da minimização do AFD”. Se escolhêssemos analisar primeiro o estado (q₁, q₂) , devido à condição δ(q₁, 1)=q₀ e δ(q₂, 1)=q₃, não saberíamos se (q₁, q₂) é equivalente ou não porque ainda não sabemos se (q₀, q₃) o é. Neste caso, devemos colocar um ponteiro de (q₀, q₃) para (q₁, q₂) nos alertando que se no futuro formos marcar (q₀, q₃) como não equivalentes, devemos seguir este ponteiro e marcar também (q₁, q₂). A situação pode ser desenhada na tabela “Dependência entre estados na minimização do AFD”:

Depois disso, ao visitarmos (q₀, q₃) , toda a tabela ficará marcada como não equivalente, conforme obtivemos anteriormente. Note que alguns autores representam a marcação de ponteiros de forma diferente, a escolhida neste texto é aquela que é mais conveniente para a programação. É interessante mostrar mais um exemplo, onde existam estados equivalentes.

Vamos analisar um novo AFD na figura abaixo:

Ao minimizarmos este AFD, em primeiro lugar devemos marcar como não equivalentes os estados finais com os não finais e vice-versa.

Falta analisarmos os pares: (q₀, q₃) e (q₁, q₂). Começaremos com (q₀, q₃) . Neste caso, temos que:

• δ(q₀, 0)=q₁ e δ(q₃, 0)=q₂
• δ(q₀, 1)=q₂ e δ(q₃, 1)=q₁

Ambas as linhas dependem do par e devemos indicar a dependência por um ponteiro, obtendo a tabela abaixo:

Finalmente analisamos (q₁, q₂) :

• δ(q₁, 0)=δ(q₂, 0)
• δ(q₁, 1)=q₀ e δ(q₂, 1)=q₃

Obtemos uma dependência circular na tabela abaixo:

Chegamos ao final do algoritmo e os pares (q₀, q₃) e (q₁, q₂) não foram marcados. Podemos considerar todos os pares não marcados como equivalentes. Portanto, podemos juntar (q₀, q₃) em um único estado, o mesmo se dá para (q₁, q₂) . Desenhamos o autômato minimizado na figura abaixo:

Vimos que todo o AFND pode ser transformado em um AFD equivalente e que existe um algoritmo para encontrar o menor AFD possível. Considere o AFD da figura “Autômato Finito Determinístico”. Ele reconhece a linguagem L_i0= {w|w tem número ímpar de 0’s}. Como construir um AFD que reconheça o complemento desta linguagem? Basta simplesmente marcar os estados não finais como finais e vice-versa. Assim, as cadeias reconhecidas serão aquelas que não eram reconhecidas anteriormente. O AFD obtido, após renomearmos os estados, é o da figura abaixo.

Uma vez que podemos construir um AFD para toda a linguagem regular e vice-versa, a consequência desta construção é que as linguagens regulares são fechadas sob complemento, isto é, se L é uma linguagem regular, então seu complemento, , também o é. Podemos agora considerar um autômato finito determinístico bem semelhante, que reconhece as cadeias sobre Σ={0, 1} que tem uma quantidade ímpar de 1’s. A figura abaixo exibe este AFD.

Um problema importante é: dados os AFDs M₁ e M₂ como fazer um AFD que reconheça a linguagem T(M₁)∩T(M₂)? Tomando os AFDs M₁=(Q₁, Σ, δ₁, q₀, F₁) da figura “AFD que reconhece o complemento da linguagem L_i0” e M₂=(Q₂, Σ, δ₂, r₀, F₂) da figura “AFD que reconhece cadeias com número ímpar de 1 ́s”, como fazer um AFD que reconheça as cadeias que tem um número par de 0’s e ímpar de 1’s? Vamos fazer isso construindo o AFD produto, M₃=(Q₃, Σ, δ₃, p₀, F₃)=M₁×M₂, no qual o conjunto de estados é o produto cartesiano dos conjuntos de estados dos AFDs originais, isto é, Q₃=Q₁×Q₂ e no qual a função de transição consiste em aplicar as funções de transição em paralelo, isto é, δ₃ ((q, r), a)=(δ₁(q, a), δ₂(r, a)). Escolhemos como estado inicial p₀=(q₀, r₀) e marcamos como estados finais os estados (q, r) onde q∈F₁ e r∈F₂. O autômato obtido é o da figura abaixo:

Observe que o AFD obtido possui certas simetrias. Sempre que lemos um ‘0’, passamos do lado esquerdo para o lado direito, ou do direito para o esquerdo. Sempre que lemos um ‘1’, passamos da parte de cima para a parte de baixo, ou o contrário. Portanto, a parte da esquerda tem sempre uma quantidade par de 0’s e a parte de baixo tem sempre uma quantidade ímpar de 1’s.

Uma vez que uma linguagem é regular se, e somente se, é reconhecida por um AFD, a construção acima nos assegura que a classe das linguagens regulares é fechada sob a operação de interseção, isto é, dadas as linguagens regulares L₁ e L₂ , a linguagem L₁∩L₂ também é uma linguagem regular.