Linguagens e Autómatos

Alfabetos, Palavras e Linguagens

Definimos um alfabeto como um conjunto finito não-vazio (de símbolos). Um alfabeto costuma ser representado pela gregra letra Σ\Sigma.

Exemplo de Alfabeto

Um exemplo de um alfabeto é o conjunto {a,b,c}\{a,b,c\}

Definimos uma palavra sobre um alfabeto Σ\Sigma como uma sequência finita de elementos de Σ\Sigma. O conjunto de todas as palavras constituídas pelos símbolos do alfabeto Σ\Sigma é representado por Σ\Sigma^*.
Existe uma palavra, a que chamamos palavra vazia e representamos por ϵ\epsilon que satisfaz ϵΣ\epsilon \in \Sigma^* para qualquer alfabeto Σ\Sigma.

Exemplo de Palavra

O conjunto de palavras sobre o alfabeto {a,b,c}\{a,b,c\} contém, por exemplo, as palavras a,ab,cccc,cbabcaa, ab, cccc, cbabca. Contudo, não contém as palavras dd, abababaeabababae, ffffffffffff.

Nota

Para um alfabeto Σ\Sigma com nn elementos, o número de palavras de tamanho kk sobre esse alfabeto é nkn^k.
Nomeadamente, a única (n0=1n^0 = 1) palavra de tamanho 00 é a palavra vazia ϵ\epsilon.

Operações sobre palavras

Para uma palavra ω\omega definimos a operação ωR\omega^R como a operação de reversão da palavra.
Por exemplo, para ω=1101\omega = 1101, temos que ωR=1011\omega^R = 1011.

Definimos ainda a operação binária de concatenação ω.σ\omega . \sigma.
Por exemplo, para ω=1101\omega = 1101 e σ=010\sigma = 010 temos que ω.σ=1101010\omega . \sigma = 1101010.
Temos nomeadamente que, ωΣ,ω.ϵ=ϵ.ω=ω\forall \omega \in \Sigma^*, \omega . \epsilon = \epsilon . \omega = \omega.
Note-se que esta operação não é comutativa, mas é associativa.

Para nN0n \in \mathbb{N}_0, denotamos por ωn\omega^n à palavra que resulta da concatenação de ω\omega consigo própria nn vezes. Mais precisamente,

ωn={ϵ,se n=0ω.ωn1,se n0\omega ^n = \begin{cases} \epsilon, & \text{se } n = 0 \\ \omega . \omega^{n-1}, & \text{se } n \neq 0 \end{cases}

Usamos ainda a notação ω| \omega | para representar o comprimento da palavra ω\omega.
Por exemplo, 010=3|010| = 3 e ϵ=0|\epsilon|=0.
Para qualquer 0<nω0 < n \leq |\omega|, usamos ωn\omega_n para nos referir ao nn-ésimo símbolo da palavra ω\omega. Por exemplo, para ω=010\omega = 010 tem-se que ω1=0\omega_1 = 0, ω2=1\omega_2 = 1 e ω3=0\omega_3 = 0.

Uma linguagem sobre o alfabeto Σ\Sigma é qualquer conjunto LΣL \subset \Sigma^*.

Operações sobre Linguagens

Damos o nome de linguagem complementar de LL à linguagem L=ΣL\overline{L} = \Sigma^* \setminus L.
Denotamos por LΣ\mathcal{L}^\Sigma o conjunto de todas as linguagens sobre Σ\Sigma.

Dadas duas linguagens L1,L2LΣL_1, L_2 \in \mathcal{L}^\Sigma, definimos a concatenação das linguagens como sendo a linguagem L1.L2={uv:uL1,vL2}L_1 . L_2 = \{ uv : u \in L_1, v \in L_2 \}.

Definimos ainda o fecho de Kleene de uma linguagem LL à linguagem L={u1.u2..un:nN0,u1,u2,,unL}L^* = \{u_1 . u_2 . \cdots . u_n : n \in \mathbb{N}_0, u_1, u_2, \cdots, u_n \in L \}

Exemplo de Linguagem

Um exemplo de uma linguagem sobre o alfabeto {0,1}\{0, 1\} é as palavras que acabam com exatamente três 11's.

As linguagens no sentido mais corrente da palavra (Português, Inglês, Mandarim) ou mesmo as linguagens de programação são linguagens de acordo com esta definição. Têm um alfabeto (no caso do português, corresponde às letras - minúsculas, maiúsculas, acentuadas e não acentuadas -, bem como outros símbolos - !, ?, ., por exemplo) que, quando de acordo com uma regra (muito complexa, claro) formam palavras "aceites", isto é, palavras que estão de acordo com as regras da linguagem.

Autómatos

Autómatos Finitos Determinísticos

Um autómato finito determinístico (AFD) é definido como um quíntuplo (Σ,Q,qin,F,δ)(\Sigma, Q, q_{in}, F, \delta) tal que

  • Σ\Sigma é um alfabeto;
  • QQ é um conjunto finito não vazio de estados;
  • qinQq_{in} \in Q é o estado inicial;
  • FQF \subset Q é um conjunto de estados finais;
  • δ:Q×ΣQ\delta: Q \times \Sigma \to Q é uma função de transição.

Cada AFD define uma liguagem sobre o seu alfabeto Σ\Sigma.

Dizemos que um autómato é total se a função de transição estiver definida para todo o elemento em Q×ΣQ \times \Sigma, isto é, se a função de transição em cada estado estiver definida para todas as letras.
Um autómato não total pode ser convertido num autómato total da seguinte forma:

  • adiciona-se um estado não final qq';
  • extende-se a função de transição tal que δ(q,a)=q\delta(q, a) = q' para todo o par (q,a)Q×Σ(q, a) \in Q \times \Sigma tal que a função de transição não fosse definida;
  • define-se δ(q,a)=q\delta(q', a) = q', para todo o aΣa \in \Sigma. É conveniente pensar neste estado qq' como um "estado lixo".

Para um AFD (Σ,Q,qin,F,δ)(\Sigma, Q, q_{in}, F, \delta) definimos a função de transição estendida deste autómato como a função δ:Q×ΣQ\delta^* : Q \times \Sigma^* \to Q tal que

δ(q,w)={q,se w=ϵδ(δ(q,a),w)se w=a.w\delta^*(q, w) = \begin{cases} q, & \text{se } w = \epsilon \\ \delta^*(\delta(q,a), w') & \text{se } w=a.w' \end{cases}

para cada qQq \in Q, aΣa \in \Sigma e wΣw \in \Sigma^*.
Entenda-se esta função como a função que, dado um estado inicial e uma palavra, devolve o estado que resulta da aplicação da função de transição do autómato às sucessivas letras da palavra.

Dizemos que uma palavra wΣw \in \Sigma^* é aceite por um AFD se δ(qin,w)F\delta^*(q_{in}, w) \in F.
Ao conjunto das palavras aceites por um AFD DD, L(D)={wΣ:δ(qin,w)F}L(D) = \{w \in \Sigma^* : \delta^*(q_{in}, w) \in F\} damos o nome de linguagem reconhecida por esse AFD.

Grafos de AFD's

Estas entidades são normalmente representadas e entendidas de acordo com grafos como o que mostramos abaixo. Para caractirizar rigorosamente esta linguagem é útil considerar a extensão a Σ\Sigma^* da função de transição do AFD.

Grafo de um AFD

Este gráfico representa o autómato cujo:

  • alfabeto é {a,b,c}\{a,b,c\}
  • conjunto de estados é {qin,q1,q2}\{q_{in}, q_1, q_2\};
  • estado inicial é qinq_{in};
  • conjunto de estados finais é {q1}\{q_1\};
  • função de transição é tal que
    δabcqinq1q1q1q2q2q2q1q2q2\begin{array}{c|ccc} \delta & a & b & c \\ \hline q_{in} & q_1 & & \\ q_1 & q_1 & q_2 & q_2 \\ q_2 & q_1 & q_2 & q_2 \end{array}

Mais genericamente, a representação gráfica de um autómato é tal que:

  • os estados correspondem aos vértices do grafo;
  • o estado inicial é aquele em que entra a seta sem origem \rightarrow;
  • os estados finais são os rodeados;
  • as arestas (dirigidas) indicam a definição da função δ\delta.

Uma linguagem LΣL \subset \Sigma^* diz-se regular se existe um AFD DD com alfabeto Σ\Sigma tal que L(D)=LL(D) = L. Ou seja, uma linguagem é regular se for reconhecida por um AFD. Denota-se por REGΣ\mathcal{REG}^\Sigma o conjunto de todas as linguagens regulares com alfabeto Σ\Sigma.
Usa-se apenas REG\mathcal{REG} em vez de REGΣ\mathcal{REG}^\Sigma sempre que o alfabeto esteja subentendido ou não seja importante o contexto.

Equivalência e Minimização de AFD's

Dizemos que dois AFD's são equivalentes se reconhecerem a mesma linguagem.
Para estudar a equivalência de AFD's, introduzimos as seguintes definições:
Para um AFD D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) dizemos que um estado qQq \in Q é:

  • acessível se existe ωΣ\omega \in \Sigma^* tal que δ(qin,ω)=q\delta^*(q_{in}, \omega) = q. Por outras palavras, um estado é acessível se for alcançável a partir da origem;
  • produtivo se existe ωΣ\omega \in \Sigma^* tal que δ(q,ω)F\delta^*(q, \omega) \in F. Por outras palavras, um estado é produtivo se for possível chegar a um estado final a partir dele;
  • útil se for acessível e produtivo, inútil caso contrário.

Introduzimos abaixo o algoritmo de procura de estados notáveis (APEN):

APEN

Apresentamos agora um algoritmo para a procura de estados notáveis.
O algoritmo recebe como input um AFD D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) e dá como output um tuplo (Ac,Prod,Ut,In)(Ac, Prod, Ut, In) com, respetivamente, os estados acessíveis, produtivos, úteis e inúteis de DD.

  1. Ac:={qin}Ac := \{q_{in}\};
  2. Aux:=aΣ{δ(qin,a)}Aux := \bigcup_{a \in \Sigma} \{ \delta(q_{in}, a) \};
  3. enquanto AuxAcAux \nsubseteq Ac
    1. Ac:=AcAuxAc := Ac \cup Aux;
    2. Aux:=aΣ{δ(p,a):pAux}Aux := \bigcup_{a \in \Sigma} \{ \delta(p, a) : p \in Aux \};
      Estados acessíveis determinados
  4. Prd:=FPrd := F;
  5. Aux:=aΣ{p:δ(p,a)F}Aux := \bigcup_{a \in \Sigma} \{ p : \delta(p, a) \in F \};
  6. enquanto AuxPrdAux \nsubseteq Prd
    1. Prd:=PrdAuxPrd := Prd \cup Aux;
    2. Aux:=aΣ{p:δ(p,a)Aux}Aux := \bigcup_{a \in \Sigma} \{ p : \delta(p, a) \in Aux \};
      Estados produtivos determinados
  7. Ut:=AcPrdUt := Ac \cap Prd;
  8. In:=QUtIn := Q \setminus Ut.
    Estados úteis e inúteis determinados

Temos que a execução deste algoritmo termina sempre e identifica corretamente os estados acessíveis (AcAc), produtivos (PrdPrd), úteis (UtUt) e inúteis (InIn).

Vamos então tentar compreender o que o algoritmo acima está a fazer:

  • Numa primeira fase (passos 1 a 3), vamos descobrir quais são os estados acessíveis. Intuitivamente, podemos fazer isto começando em qinq_{in} e fazendo uma procura (BFS) no grafo do AFD. À medida que o fazemos, colocamos esses estados no conjunto de estados acessíveis;
  • Numa segunda fase (passos 4 a 6), vamos determinar os estados produtivos. Estes são aqueles que vão levar a estados finais. Então, começamos exatamente nos estados finais e fazemos também uma procura (BFS), mas desta vez no sentido contrário das setas do grafo do AFD. À medida que descobrimos os estados produtivos, colocamo-los no conjunto apropriado.
  • Finalmente, determinamos os estados úteis e inúteis de acordo com a sua definição.

Para facilitar a compreensão do algoritmo, pode ser útil vê-lo em prática no exemplo seguinte.

Exemplo de aplicação do APEN

Tenhamos um AFD tal que:

Autómato Inicial - APEN

Ora, procurando seguir os passos descritos na descrição acima:

  • Descobrir os estados acessíveis passa por realizar uma BFS a partir do estado inicial, qinq_{in} - todos os estados encontrados dizem-se acessíveis:

    Começamos com o conjunto de estados acessíveis a conter apenas qinq_{in}:

    BFS - Estados acessíveis (1)

    Logo de seguida, começamos a BFS partindo desse mesmo estado:

    BFS - Estados acessíveis (2)

    Encontrámos, a distância 11 do estado inicial, os estados q1,q2,q5q_1, q_2, q_5. A BFS continua então, partindo desses mesmos estados, tal que:

    BFS - Estados acessíveis (3)

    Podemos observar que a procura encontrou aqui q4q_4. Mais ainda, temos que não há mais caminhos por onde prosseguir. A procura termina, portanto, e o conjunto de estados acessíveis foi obtido.

  • De seguida, determinar os estados produtivos: fazer BFS's, partindo de cada estado final, pelo "autómato transposto":

    Inicialmente, o grafo transposto encontra-se assim (os estados finais estão, claro, no conjunto dos estados produtivos): BFS's - Estados produtivos (1)

    Realizamos aqui o primeiro passo da BFS - partindo dos estados finais, q1q_1 e q4q_4, realizamos uma procura pelos estados a que podemos chegar a partir deles: BFS's - Estados produtivos (2)

    Repetimos o passo anterior, desta vez partindo dos estados que obtivemos acima: qinq_{in} e q2q_2: BFS's - Estados produtivos (3)

    A partir dos estados acima obtidos, não podemos atingir qualquer outro estado, pelo que o algoritmo pára e temos determinado o conjunto de estados produtivos do autómato.

    Ora, temos então dois conjuntos em mãos:

Estados Acessiveis={qin,q1,q2,q4,q5}Estados Produtivos={qin,q1,q2,q3,q4,q5,q6}\text{Estados Acessiveis} = \{q_{in}, q_1, q_2, q_4, q_5\}\\ \text{Estados Produtivos} = \{q_{in}, q_1, q_2, q_3, q_4, q_5, q_6\}

Pela definição da utilidade de um estado (um estado diz-se útil caso seja acessível e produtivo), podemos dizer que a interseção dos conjuntos acima corresponde ao conjunto dos estados úteis do autómato, e que portanto:

Estados Uˊteis=AcPrd={qin,q1,q2,q4,q5}Estados Inuˊteis=QUt={q3,q6,q7}\text{Estados Úteis} = Ac \cap Prd = \{q_{in}, q_1, q_2, q_4, q_5\}\\ \text{Estados Inúteis} = Q \setminus Ut = \{q_3, q_6, q_7\}
Prova da correção do algoritmo APEN

Resume-se essencialmente a: BFS funciona.

Definimos agora dois estados p,qQp,q \in Q de um AFD D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) como

  • equivalentes se, para cada ωΣ\omega \in \Sigma^*, temos que δ(p,ω)Fδ(q,ω)F\delta^*(p, \omega) \in F \Leftrightarrow \delta^*(q, \omega) \in F;
  • distinguíveis se não forem equivalentes. Neste caso existe pelo menos uma palavra ωΣ\omega \in \Sigma^* tal que δ(p,ω)Fδ(q,ω)F\delta^*(p, \omega) \in F \wedge \delta^*(q, \omega) \notin F (ou vice-versa). Dizemos que ω\omega distingue pp e qq;

Vamos agora identificar critérios para distinguir estados. A partir disto, poderemos descrever um algoritmo para encontrar estados equivalentes e, consequentemente, determinar um algoritmo que minimize um AFD.

Seja D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) um AFD e sejam p,qQp,q \in Q e aΣa \in \Sigma. Temos que:

  1. Se pFp \in F, e qFq \notin F então pp e qq são distinguíveis;
  2. Se pp é produtivo e qq não, então pp e qq são distinguíveis;
  3. Se δ(p,a)\delta(p,a) é produtivo e δ(q,a)\delta(q, a) não está definido, então pp e qq são distinguíveis;
  4. Se pp' e qq' são estados distinguíveis, δ(p,a)=p\delta(p,a) = p' e δ(q,a)=q\delta(q,a) = q', então pp e qq são distinguíveis. Equivalentemente, se pp e qq são equivalentes, então δ(p,a)\delta(p,a) e δ(q,a)\delta(q,a) também o são para qualquer aΣa \in \Sigma;

Ver a prova destas propriedades pode ajudar a compreendê-las.

Prova
  1. A palavra ϵ\epsilon distingue os estados;
  2. Se pp é produtivo, existe ωΣ\omega \in \Sigma^* tal que δ(p,ω)F\delta^*(p, \omega) \in F. Contudo, como qq não é produtivo, δ(q,ω)F\delta^*(q, \omega) \notin F, pelo que a palavra ω\omega distingue os estados;
  3. Sabemos que podemos adicionar um estado lixo ao AFD de forma que ficamos com um AFD equivalente. Se δ(q,a)\delta(q,a) não está definido, no autómato com estado lixo vamos ver que δ(q,a)=qlixo\delta(q,a) = q_{lixo}, que é um estado não produtivo. Podemos então aplicar a condição dois a δ(p,a)\delta(p, a) e qlixoq_{lixo};
  4. Seja ω\omega uma palavra que distingue pp' e qq'. Então, a palavra a.ωa.\omega distingue pp e qq.

Definimos ainda PDP_D como sendo o conjunto de todos os pares {p,q}Q\{p,q\} \subset Q.

Tendo em conta estes critérios e este conjunto, introduzimos agora um algoritmo de procura de estados distinguíveis (APED).

APED

O algoritmo recebe como input o AFD D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) e o seu output é um conjunto DstPDDst \subset P_D de pares de estados distinguíveis.

  1. Δ:={{p,q}Q:pF,qF}{{p,q}Q:p produtivo e q na˜o produtivo}{{p,q}Q:aΣ:δ(p,a) produtivo e δ(q,a) na˜o definido};\begin{matrix*}[l] \Delta := &\{\{p,q\} \subset Q : p \in F, q \notin F \} \, \cup \\ &\{\{p,q\} \subset Q : p \text{ produtivo e } q \text{ não produtivo} \} \, \cup \\ &\{\{p,q\} \subset Q : \exists a \in \Sigma: \delta(p,a) \text{ produtivo e } \delta(q,a) \text{ não definido} \}; \end{matrix*}
  2. Aux:={{p,q}Δ:aΣ:{δ(p,a),δ(q,a)}Δ}Aux := \{ \{p,q\} \notin \Delta: \exists a \in \Sigma: \{\delta(p,a), \delta(q,a) \} \in \Delta \};
  3. enquanto ΔAuxPD\Delta \cup Aux \neq P_D e AuxAux \neq \emptyset
    1. Δ:=ΔAux\Delta := \Delta \cup Aux;
    2. Aux:={{p,q}Δ:aΣ:{δ(p,a),δ(q,a)}Aux}Aux := \{ \{p,q\} \notin \Delta: \exists a \in \Sigma: \{ \delta(p,a), \delta(q,a) \} \in Aux \};
  4. Dst:=ΔAuxDst := \Delta \cup Aux.

O que o algoritmo acima faz é o seguinte:
Para começar, determinar os estados distinguíveis de acordo com os 3 primeiros critérios. Então, enquanto os houver, determinar mais estados distinguíveis de acordo com o 4º critério. À medida que estes estados vão sendo encontrados, vão sendo agrupados no conjunto DstDst.

A execução deste algoritmo termina sempre retornando exatamente o conjunto de pares de estados distinguíveis do AFD.

Para ajudar a compreender este algoritmo pode ser útil vê-lo em prática abaixo.

Exemplo de aplicação do APED

Consideremos um AFD tal que:

AFD - APED

A nossa primeira tarefa será preencher Δ\Delta segundo os três critérios iniciais:

  • Num primeiro momento, organizar pares onde um elemento é um estado final e o outro é um estado não final (a ordem é irrelevante) - temos, neste momento:
Δ={[p,q],[q,s],[q,r]}\Delta = \{[p, q], [q, s], [q, r]\}
  • De seguida, criar pares onde um elemento é um estado produtivo e o outro não - fazendo a BFS mencionada acima, verificamos que todos os estados são produtivos, pelo que Δ\Delta permanece igual.

  • Por fim, encontrar todos os pares tais que um dos vértices transita, segundo um dado símbolo, para um estado produtivo, e o outro não tem qualquer transição associada a esse símbolo. Verificar esta condição pode ser mais fácil seguindo algumas heurísticas:

    • Num primeiro momento, verificar todos os estados para os quais nem todos os símbolos têm uma transição definida - aqui, pp não tem transição definida para bb e cc, e é o único nessa situação. Podemos a partir daqui depreender que qualquer par obtido através desta "procura" terá de envolver pp.

    • Obtidos símbolos sem transição definida para pp, aqui bb e cc, procuramos os estados que têm transição definida para os mesmos e onde essa transição leve a um estado produtivo. Neste caso, qq tem transições segundo bb e cc para estados produtivos, tais como rr e ss, pelo que podemos admitir que os pares criados por esta procura são {[p,q],[p,r],[p,s]}\{[p, q], [p, r], [p, s]\}.

    No final destes três passos, ficamos com:

    Δ={[p,q],[q,s],[q,r],[p,r],[p,s]}.\Delta = \{[p, q], [q, s], [q, r], [p, r], [p, s]\}.

O resto do algoritmo normalmente faz-se recorrendo a uma tabela, onde cada linha e coluna correspondem a um dos estados do autómato (só se utiliza metade da tabela, já que é simétrica). A tabela corresponde ao autómato em questão seria:

ss \\backslash
rr \\backslash \\backslash
qq \\backslash \\backslash \\backslash
pp \\backslash \\backslash \\backslash \\backslash
pp qq rr ss

Cada entrada na tabela corresponde a um dos pares de estados possíveis. Começamos por preencher a tabela com uma cruz em cada entrada que corresponde a um par em Δ\Delta. Seria, portanto:

ss ×\times ×\times \\backslash
rr ×\times ×\times \\backslash \\backslash
qq ×\times \\backslash \\backslash \\backslash
pp \\backslash \\backslash \\backslash \\backslash
pp qq rr ss

Entramos aqui na secção porventura mais desagradável: percorrer todos os pares de Δ\Delta (que tenham uma cruz na tabela, portanto), e para cada um deles, verificar se existe um par que não esteja em Δ\Delta tal que, segundo transições por um mesmo símbolo, chegam ao par de estados original (e adicionar qualquer estado encontrado à tabela). Assim que um par é (ou não) encontrado, a cruz na tabela é rodeada por um círculo (para anotar que já foi explorado).

Ora, procuremos então percorrerΔ\Delta:

  • todos os estados que incluem pp não adicionam pares a Δ\Delta, já que não há qualquer estado a transicionar para pp sequer. A tabela fica, então:
ss ×\textcircled\times ×\times \\backslash
rr ×\textcircled\times ×\times \\backslash \\backslash
qq ×\textcircled\times \\backslash \\backslash \\backslash
pp \\backslash \\backslash \\backslash \\backslash
pp qq rr ss
  • olhando para o estado [q,r][q, r], podemos notar que não há qualquer par de estados que não esteja em Δ\Delta e em que, segundo o mesmo símbolo, leve ao estado [q,r][q, r]. Não existe qualquer estado segundo aa a transicionar para rr, nem nenhum estado que segundo bb ou cc transicione para qq, pelo que o estado dá-se por explorado sem adicionar nada de novo à tabela (sem ser circular a cruz respetiva a [q,r][q, r]).
ss ×\textcircled\times ×\times \\backslash
rr ×\textcircled\times ×\textcircled\times \\backslash \\backslash
qq ×\textcircled\times \\backslash \\backslash \\backslash
pp \\backslash \\backslash \\backslash \\backslash
pp qq rr ss
  • por fim, resta explorar [q,s][q, s]. Não existe qualquer estado segundo aa a transicionar para ss, nem nenhum estado que segundo bb ou cc transicione para qq, pelo que o estado dá-se por explorado sem adicionar nada de novo à tabela (sem ser circular a cruz respetiva a [q,s][q, s]).
ss ×\textcircled\times ×\textcircled\times \\backslash
rr ×\textcircled\times ×\textcircled\times \\backslash \\backslash
qq ×\textcircled\times \\backslash \\backslash \\backslash
pp \\backslash \\backslash \\backslash \\backslash
pp qq rr ss

Todas as entradas com cruzes na tabela foram oficialmente exploradas. Os estados distinguíveis correspondem, então, às entradas com cruzes da tabela: podemos afirmar que todos os pares de estados do autómato, exceto [r,s][r, s], são distinguíveis entre si.

Além de permitir calcular o conjunto dos pares de estados distinguíveis de um AFD e, consequentemente, o conjunto dos seus pares de estados equivalentes, o APED pode também ser usado para determinar se dois AFD's D1D1 e D2D2 são ou não equivalentes.
Isto é feito através do algoritmo de teste à equivalência de AFD's (ATEQ):

ATEQ

O algoritmo recebe como input dois AFD's D1=(Σ,Q1,qin1,F1,δ1)D_1 = (\Sigma, Q_1, q_{in}^1, F_1, \delta_1) e D2=(Σ,Q2,qin2,F2,δ2)D_2 = (\Sigma, Q_2, q_{in}^2, F_2, \delta_2) tais que Q1Q2=Q_1 \cap Q_2 = \emptyset, e o seu output é um booleano que indica se os AFD's são ou não equivalentes.

  1. construir o AFD D=(Σ,Q1Q2,qin1,F1F2,δ)D = (\Sigma, Q_1 \cup Q_2, q_{in}^1, F_1 \cup F_2, \delta) em que
    δ(q,a)={δ1(q,a)se estiver definido para qQ1δ2(q,a)se estiver definido para qQ2indefinidocaso contraˊrio\delta(q, a) = \begin{cases} \delta_1(q,a) & \text{se estiver definido para } q \in Q_1 \\ \delta_2(q,a) & \text{se estiver definido para } q \in Q_2 \\ \text{indefinido} & \text{caso contrário} \end{cases}
  2. Dst:=APED(D)Dst := APED(D);
  3. se {qin1,qin2}Dst\{ q_{in}^1, q_{in}^2 \} \in Dst return false
    caso contrário return true.

Este algoritmo termina sempre, identificando como equivalentes dois AFD's se e só se eles são equivalentes.

Prova da correção do ATEQ

Verifica-se que, se qQ1q \in Q_1, então δ(q,a)Q1\delta(q, a) \in Q_1, para qualquer aΣa \in \Sigma.
Indutivamente, temos então que para qualquer ωΣ\omega \in \Sigma^*, se qQ1q \in Q_1, então δ(q,ω)Q1\delta^*(q, \omega) \in Q_1.
Consequentemente, se δ(q,ω)F\delta(q, \omega) \in F para qQ1q \in Q_1, então δ(q,ω)F1\delta(q, \omega) \in F_1.
Estas propriedades verificam-se analogamente para qQ2q \in Q_2.

Podemos inferir então que {qin1,qin2}Dst\{ q_{in}^1, q_{in}^2 \} \in Dst equivale a dizer que existe uma palavra ωΣ\omega \in \Sigma^* tal que apenas um dos dois se verifica:

  • δ(qin1,ω)F\delta(q_{in}^1, \omega) \in F;
  • δ(qin2,ω)F\delta(q_{in}^2, \omega) \in F.

consequentemente, já que qin1Q1q_{in}^1 \in Q_1 e qin2Q2q_{in}^2 \in Q_2, apenas um dos dois se verifica:

  • δ(qin1,ω)F1\delta(q_{in}^1, \omega) \in F_1;
  • δ(qin2,ω)F2\delta(q_{in}^2, \omega) \in F_2.

ou seja, a palavra ω\omega é reconhecida exatamente num dos autómatos D1D_1 e D2D_2.

Estamos agora prontos para resolver problemas de minimização de AFD's.
Um AFD diz-se mínimo se não existir nenhum outro AFD que lhe seja equivalente e tenha menos estados.

Para determinar o AFD mínimo a um AFD DD definimos a partição induzida pelos estados equivalentes de DD como o conjunto {C[q]:qQ}\{C[q] : q \in Q\} em que C[q]={q}{pQ:p,q sa˜o equivalentes}C[q] = \{ q \} \cup \{ p \in Q : p, q \text{ são equivalentes} \}, para cada qQq \in Q.
Note-se como C[q]C[p]=C[q] \cap C[p] = \emptyset para pp e qq distinguíveis e qQC[q]=Q\bigcup_{q \in Q} C[q] = Q, pelo que o conjunto definido é de facto uma partição.

Estamos agora em posição de introduzir o algoritmo de minimização de um AFD:

Minimização de AFD

Dado um AFD D=(Σ,Q,qin,F,δ)D = (\Sigma, Q, q_{in}, F, \delta) a minimização de DD é o AFD mDm_D construído da seguinte forma:

  • se F=F = \emptyset, então mDm_D tem apenas um estado inicial não final, e a sua função de transição não está definida para qualquer letra;
  • caso contrário, mD=(Σ,Qm,qinm,Fm,δm)m_D = (\Sigma, Q_m, q_{in}^m, F_m, \delta_m) em que:
    • Qm={C0,C1,,Cn}Q_m = \{ C_0, C_1, \cdots, C_n \} é a partição do conjunto dos estados úteis de DD induzida pelos estados equivalentes, com qinC0q_{in} \in C_0;
    • qinm=C0q_{in}^m = C_0;
    • Fm={CiQm:CiF}F_m = \{ C_i \in Q_m : C_i \cap F \neq \emptyset \};
    • δm:Qm×ΣQm\delta_m : Q_m \times \Sigma \to Q_m é tal que:
      δm(Ci,a)={Cjse δ(q,a)Cj para algum qCiindefinidocaso contraˊrio\delta_m(C_i, a) = \begin{cases} C_j & \text{se } \delta(q, a) \in C_j \text{ para algum } q \in C_i \\ \text{indefinido} & \text{caso contrário} \end{cases}

Observações

É relevante para o algoritmo acima notar que, para um conjunto CC de estados equivalentes:

  • Se existe um estado produtivo em CC, então CC só tem estados produtivos. Assim sendo, ao ignorarmos estados inúteis não podemos ignorar estados inúteis por equivalência;

  • Se FCF \cap C \neq \emptyset, então CFC \subset F. Isto é, se há um estado final em CC, todos os estados de CC são finais. Isto é uma consequência direta do primeiro critério de distinção de estados e faz com que a definição de estados finais de mDm_D seja não ambígua;

  • Se δ(q,a)=p\delta(q,a) = p para q,pQq, p \in Q e aΣa \in \Sigma, então, para cada qC[q]q' \in C[q] temos que um dos dois se verifica:

    • δ(q,a)\delta(q', a) não está definido e pp não é produtivo;
    • δ(q,a)C[p]\delta(q', a) \in C[p].

    Isto faz com que a função δm\delta_m esteja bem definida. Note-se que desta propriedade resulta que δm(C,a)\delta_m(C, a) não pode oferecer dois valores diferentes, nem pode ser indefinida para alguns valores e definida para outros (uma vez que em mDm_D consideramos apenas estados úteis).

Prova de equivalência de mDm_D a DD

Seja ωΣ\omega \in \Sigma^* tal que δ(q,ω)F\delta^*(q, \omega) \in F.
Se ω=ϵ\omega = \epsilon, então δm(C[q],ω)Fm\delta_m^*(C[q], \omega) \in F_m.
Caso contrário, ω=a.ω\omega = a.\omega' para aΣa \in \Sigma e ωΣ\omega' \in \Sigma^*.
Segundo o quarto critério de distinção de estados, temos que se qC[q]q' \in C[q] então δ(q,a)C[δ(q,a)]\delta(q', a) \in C[\delta(q, a)].
Assim sendo, por indução, temos que se δ(q,ω)F\delta^*(q, \omega) \in F, então δm(C[q],ω)Fm\delta_m^*(C[q], \omega) \in F_m.
Nomeadamente, uma palavra que seja aceite em DD, será também aceite em mDm_D.

Explicado de uma forma menos rigorosa, o que estamos a constatar é que à medida que vai "lendo símbolos do alfabeto", o AFD mDm_D está sempre num estado que corresponde à "classe de equivalência" do estado em que DD está depois de ler esses mesmos símbolos.
Ora, se ao fim dessa leitura, DD está num estado final, e as classes de equivalência de estados finais em DD são estados finais em mDm_D, temos que ao fim dessa mesma leitura, mDm_D também está num estado final.
Quer isto dizer que qualquer palavra aceite por DD é também aceite por mDm_D.

Exemplo da Minimização de um AFD

Consideremos o seguinte autómato:

AFD - Minimização

Apesar do decorrer do algoritmo de procura de estados distinguíveis não constar deste exemplo, consideremos que, aquando do concluir do mesmo, a tabela é tal que:

q5q_5 ×\textcircled\times ×\textcircled\times ×\textcircled\times ×\textcircled\times \\backslash
q4q_4 ×\textcircled\times ×\textcircled\times ×\textcircled\times ×\textcircled\times \\backslash \\backslash
q3q_3 ×\textcircled\times ×\textcircled\times ×\textcircled\times \\backslash \\backslash \\backslash
q2q_2 ×\textcircled\times \\backslash \\backslash \\backslash \\backslash
q1q_1 ×\textcircled\times \\backslash \\backslash \\backslash \\backslash \\backslash
q0q_0 \\backslash \\backslash \\backslash \\backslash \\backslash \\backslash
q0q_0 q1q_1 q2q_2 q3q_3 q4q_4 q5q_5

A tabela final tem, portanto, dois pares de estados equivalentes: [q1,q2][q_1, q_2] e [q4,q5][q_4, q_5]. Ao desenhar o autómato minimizado, os estados presentes em cada par terão de estar juntos.

AFD - Minimização

Pode agora ser mais claro o porquê de considerarmos dois estados equivalentes/distinguíveis: os estados equivalentes têm, no autómato original, transições equivalentes (segundo o mesmo símbolo vão sempre para um estado num "grupo de estados equivalentes"). No caso de q1,q2q_1, q_2, por exemplo, temos que:

  • através de aa transicionam para o próprio estado em ambas as situações;
  • através de bb transicionam, em ambos os casos, para q0q_0;
  • através de cc transicionam, em ambos os casos, para um estado dentro do "par equivalente" [q4,q5][q_4, q_5] - q1q_1 para q4q_4 e q2q_2 para q5q_5.

Autómatos Finitos Não Determinísticos

Introduzimos a notação (S)\wp(S) como o conjunto dos subconjuntos do conjunto SS. Também se diz que este é o conjunto das partes de SS.

Exemplo de um Conjunto de Partes

Temos, por exemplo, que ({0,1})={,{0},{1},{0,1}}\wp(\{0,1\}) = \{\emptyset, \{0\}, \{1\}, \{0,1\}\}.

Tamanho do conjunto das partes

Se um conjunto SS tem nn elementos, o conjunto (S)\wp(S) tem 2n2^n elementos.

Prova

Isto é uma consequência de cada conjunto estar unicamente determinado pelos elementos que têm. Ora, para cada elemento, ele ou está, ou não está num dado conjunto - isto é, cada elemento tem 2 opções em relação a um dado conjunto. Sendo assim, deve haver 2n2^n subconjuntos de um conjunto de nn elementos.

Esta prova pode ser formalizada por indução.

Um autómato finito não determinístico (AFND) é definido como um quíntuplo (Σ,Q,qin,F,δ)(\Sigma, Q, q_{in}, F, \delta) tal que:

  • Σ\Sigma é um alfabeto;
  • QQ é um conjunto finito de estados;
  • qinQq_{in} \in Q é o estado inicial;
  • FQF \subset Q é um conjunto de estados finais;
  • δ:Q×Σ(Q)\delta: Q \times \Sigma \to \wp(Q) é uma função de transição.

Note-se que a diferença entre um AFND e um AFD é que a função de transição num AFD não é determinística, na medida em que não define um e um só estado. Para cada par (q,a)Q×Σ(q, a) \in Q \times \Sigma temos que δ(q,a)\delta(q, a) define o subconjunto de QQ dos estados que podem resultar da transição por aa a partir de qq.

Podemos ainda assinalar o autómato finito não determinístico como AFNDϵ^\epsilon se a função de transição tiver como domínio Q×(Σ×{ϵ})Q \times (\Sigma \times \{ \epsilon \}). Ou seja, um AFNDϵ^\epsilon é tal que pode haver transições que não são "causadas" por letra nenhuma. Nesta situação diz-se que o AFND tem movimentos-ϵ\epsilon.
A distinção entre AFND e AFNDϵ^\epsilon é negligenciada em contextos que não seja relevante. Para simplificar, pode-se assumir que um AFND está sempre dotado de movimentos-ϵ\epsilon.

Grafo de um AFND

Grafo de um AFND

Este gráfico representa o autómato cujo:

  • alfabeto é {a,b,c}\{a,b,c\}
  • conjunto de estados é {qin,q1,q2,q3,q4,q5}\{q_{in}, q_1, q_2, q_3, q_4, q_5\};
  • estado inicial é qinq_{in};
  • conjunto de estados finais é {q5}\{q_5\};
  • função de transição é tal que
    δabcϵqin{q1,q3}q1{q2}{q1}{q1}q2{q1}{q2}{q2}{q5}q3{q3}{q3}{q3,q4}{q4}q4{q5}q5\begin{array}{c|cccc} \delta & a & b & c & \epsilon \\ \hline q_{in} & \emptyset & \emptyset & \emptyset & \{ q_1, q_3 \} \\ q_1 & \{ q_2 \} & \{ q_1 \} & \{ q_1 \} & \emptyset \\ q_2 & \{ q_1 \} & \{ q_2 \} & \{ q_2 \} & \{ q_5 \} \\ q_3 & \{ q_3 \} & \{ q_3 \} & \{ q_3, q_4 \} & \{ q_4 \} \\ q_4 & \emptyset & \emptyset & \{ q_5 \} & \emptyset \\ q_5 & \emptyset & \emptyset & \emptyset & \emptyset \end{array}

Para isto, começamos por definir o fecho-ϵ\epsilon de um estado.
Seja A=(Σ,Q,qin,F,δ)A = (\Sigma, Q, q_{in}, F, \delta) um AFND. O fecho-ϵ\epsilon de um estado qQq \in Q é o conjunto qϵQq^\epsilon \subset Q tal que:

  • qqϵq \in q^\epsilon;
  • qqϵδ(q,ϵ)qϵq' \in q^\epsilon \Rightarrow \delta(q', \epsilon) \subset q^\epsilon.

Dado um subconjunto CC de QQ, o seu fecho-ϵ\epsilon é o conjunto Cϵ=qCqϵC^\epsilon = \bigcup_{q \in C} q^\epsilon.
Dito de forma corrente, o fecho-ϵ\epsilon de um estado qQq \in Q é o conjunto de estados que se conseguem obter a partir de qq apenas com movimentos-ϵ\epsilon.

Podemos então definir a função de transição estendida de um AFND A=(Σ,Q,qin,F,δ)A = (\Sigma, Q, q_{in}, F, \delta) como a função δ:Q×Σ(Q)\delta^* : Q \times \Sigma^* \to \wp(Q) tal que, para cada qQq \in Q, aΣa \in \Sigma e ωΣ\omega \in \Sigma^*:

δ(q,ω)={qϵse ω=ϵqqϵ(qδ(q,a)δ(q,ω))se ω=a.ω\delta^*(q, \omega) = \begin{cases} q^\epsilon & \text{se } \omega = \epsilon \\ \bigcup_{q' \in q^\epsilon} \left( \bigcup_{q'' \in \delta(q', a)} \delta^*(q'', \omega' ) \right) & \text{se } \omega = a.\omega' \end{cases}

Através desta função, podemos definir a palavra aceite por um AFND como qualquer palavra ωΣ\omega \in \Sigma^* tal que δ(qin,ω)F\delta^*(q_{in}, \omega) \cap F \neq \emptyset.
Dito de forma corrente, uma palavra é aceite por um AFND se houver uma sequência de estados em QQ tal que:

  • a concatenação dos símbolos das transições entre esses estados resulte na palavra em questão;
  • a sequência acabe num estado final.
Exemplo de Palavra Aceite num AFND

Consideremos o AFND que aceita todas as palavras com número ímpar de aa's ou que terminam em cc:

Palavra Aceite por um AFND

Ora, tentemos então verificar se algumas palavras são ou não aceites por este autómato:

  • tenhamos abcababcab; não deve ser aceite: não tem número ímpar de aa's nem termina em cc. As imagens abaixo procuram seguir a sequência de estados da palavra. Nenhuma delas termina num estado final, pelo que a palavra não é aceite (como esperado).

    Palavra não aceite por um AFND 1 Palavra não aceite por um AFND 2 Palavra não aceite por um AFND 3 Palavra não aceite por um AFND 4 Palavra não aceite por um AFND 5 Palavra não aceite por um AFND 6

  • por outro lado, consideremos acbaaacbaa - a palavra deve ser aceite, já que tem número ímpar de aa's. Vejamos então o caminho percorrido ao ler a palavra:

    Palavra aceite (1) por um AFND 1 Palavra aceite (1) por um AFND 2 Palavra aceite (1) por um AFND 3 Palavra aceite (1) por um AFND 4 Palavra aceite (1) por um AFND 5 Palavra aceite (1) por um AFND 6

    Como último passo, lemos aqui o símbolo vazio - podemos sempre lê-lo, e transitamos assim para o estado final desejado!

    Palavra aceite (1) por um AFND 7

A linguagem reconhecida por um AFND é o conjunto das palavras aceites por esse AFND, isto é, o conjunto L(A)={ωΣ:δ(qin,ω)F}L(A) = \{ \omega \in \Sigma^* : \delta^*(q_{in}, \omega) \cap F \neq \emptyset \}.

Exemplo de Linguagem Reconhecida por um AFND

AFND depois de remover movimentos-epsilon

Por exemplo, a linguagem reconhecida pelo AFND acima é a linguagem das palavras sobre o alfabeto {a,b,c}\{a,b,c\}^* que têm um número ímpares de aa's ou acabam em cc.

Conversão de AFND's em AFD's

Temos que todas as linguagens reconhecidas por AFND's são linguagens regulares. Por outras palavras, seja qual for o AFND, existe um AFD que reconhece a mesma linguagem que o AFND de partida. Vamos ver daqui para a frente como obter a partir de um AFND o seu AFD equivalente.

Primeiro, começamos por remover os movimentos-ϵ\epsilon:
Dado um AFND A=(Σ,Q,qin,F,δ)A = (\Sigma, Q, q_{in}, F, \delta), temos que o AFND A=(Σ,Q,qin,F,δ)A' = (\Sigma, Q, q_{in}, F', \delta') é-lhe equivalente se

  • F={qQ:qϵF}F' = \{q \in Q : q^\epsilon \cap F \neq \emptyset \};
  • δ:Q×Σ(Q)\delta' : Q \times \Sigma \to \wp(Q) é tal que δ(q,a)=qqϵ(qδ(q,a)qϵ)\delta'(q,a) = \bigcup_{q' \in q^\epsilon} \left( \bigcup_{q'' \in \delta(q', a)} q''^\epsilon \right) para cada qQq \in Q e aΣa \in \Sigma.

Pode-se entender a função δ\delta' como sendo δ\delta^* aplicada a palavras com apenas uma letra.
Desta forma, é claro que δ(q,ω)=δ(q,ω)\delta'^*(q, \omega) = \delta^*(q, \omega) (em AA', considerar os fechos-ϵ\epsilon não tem efeito) pelo que os autómatos AA e AA' reconhecem a mesma linguagem.

Remoção de movimentos-ϵ\epsilon

Vamos compreender as alterações acima:

  • Se podermos alcançar um estado final através de um movimento-ϵ\epsilon, então se considerarmos esse estado como sendo também final, as palavras reconhecidas pelo nosso AFND não mudam;
  • Para cada estado qQq \in Q vamos ver que estados conseguimos alcançar usando apenas a letra aΣa \in \Sigma. O conjunto de estados que conseguimos alcançar só com aa corresponde ao resultado de aplicar aa a todos os estados em qϵq^\epsilon e depois tirar o fecho-ϵ\epsilon do resultado. Isto é, pego em todos os estados a que consigo chegar com ϵ\epsilon, vejo onde consigo chegar com aa, e finalmente aplico ϵ\epsilon outra vez.

Fecho epsilon de um estado

Por exemplo, na imagem acima, estão assinalados que podem ser obtidos a partir de qinq_{in} com a letra bb. Todas as transições a partir de qinq_{in} passam por:

  • ver onde é possível chegar com movimentos-ϵ\epsilon. Na nossa imagem, estes primeiros movimentos estão assinalados a verde. O estado q4q_4, apesar de estar em qinϵq_{in}^\epsilon não está marcado com seta verde pois não há nenhum transição a partir de q4q_4 com bb.
  • depois, fazemos então as transições que usam a letra bb, transições estas que estão assinaladas com setas vermelhas.
  • finalmente, podemos ainda fazer mais movimentos-ϵ\epsilon, que estão assinalados a azul.

Os estados que conseguimos obter a partir de qinq_{in} com apenas um bb são os vermelhos e os azuis - {q1,q3,q4}\{ q_1, q_3, q_4 \}.

Prova da equivalência entre AA e AA'

A definição de função de transição estendida para o AFND AA' será

δ(q,ω)={qse ω=ϵqqϵ(qδ(q,a)δ(q,ω))se ω=a.ω={qse ω=ϵqδ(q,a)δ(q,ω)se ω=a.ω={qse ω=ϵqqϵ(qδ(q,a)(qqϵδ(q,ω)))se ω=a.ω\delta'^*(q, \omega) = \begin{cases} q & \text{se } \omega = \epsilon \\ \bigcup_{q' \in q^\epsilon} \left( \bigcup_{q'' \in \delta'(q', a)} \delta'^*(q'', \omega') \right) & \text{se } \omega = a.\omega' \end{cases} \\ = \begin{cases} q & \text{se } \omega = \epsilon \\ \bigcup_{q' \in \delta'(q,a)} \delta'^*(q', \omega') & \text{se } \omega = a. \omega' \end{cases} \\ = \begin{cases} q & \text{se } \omega = \epsilon \\ \bigcup_{q' \in q^\epsilon} \left( \bigcup_{q'' \in \delta(q',a)} \left( \bigcup_{q''' \in q''^\epsilon} \delta'^*(q''', \omega') \right) \right) & \text{se } \omega = a. \omega' \end{cases}

em que em cima consideramos o fecho-ϵ\epsilon de qq em AA', mas em baixo consideramos o fecho-ϵ\epsilon de qq em AA.

Ou seja, a função de transição estendida de AA' é tal que, dada uma letra aΣa \in \Sigma e um estado qQq \in Q, podemos alcançar todos os estados que podiamos em AA com essa letra (e possivelmente com movimentos-ϵ\epsilon).
Indutivamente, se dermos uma palavra ωΣ\omega \in \Sigma^* a AA', obtemos o mesmo conjunto de estados que obtiamos em AA. Consequentemente, uma palavra é aceite em