Autómatos Finitos

Pequeno Exemplo

Representação gráfica de um autómato que, numa palavra de 00's e 11's finita, verifica se o número de 00's é par e 11's é ímpar.

Auto Inic

Onde pp é par, ii ímpar e primeiro referimo-nos aos 00's e depois aos 11's.
"Ei" aponta para o estado inicial.

Autómato Finito Determinístico (AFD)

Um autómato finito determinístico é um quíntuplo D=(Q,Σ,δ,q0,F)D = (Q,\Sigma,\delta,q_0,F) onde:

  • QQ é um conjunto finito não vazio
  • q0q_0 é o estado inicial do autómato (q0Q)(q_0 \in Q)
  • Σ\Sigma é um alfabeto (conj. finito de símbolos)
  • FF estados de aceitação/finais (FQ)(F \subseteq Q)
  • δ\delta função que, com o estado atual e com σΣ\sigma \in \Sigma que recebe, transita para um novo estado (δ:Q×ΣQ)(\delta: Q \times \Sigma \rightarrow Q )
Exemplo 1

Pegando no exemplo do início onde queríamos verificar se, numa palavra de 00's e 11's, o número de 00's é par e 11's é ímpar.

Auto Inic

D=(Q,Σ,δ,q0,F)Q={pp,pi,ip,ii}Σ={0,1}δ01ppippipiiippipppiiiipiipq0=ppF={pi}D = (Q,\Sigma,\delta,q_0,F)\\ Q = \{pp,pi,ip,ii\}\\ \Sigma = \{0,1\}\\ \begin{array}{c|c|c} \delta & 0 & 1 \\ \hline pp & ip & pi\\ \hline pi & ii & pp \\ \hline ip & pp & ii \\ \hline ii & pi & ip \end{array}\\ q_0 = pp\\ F = \{pi\} \\

Relembrar que queríamos ver se a palavra tinha um número par de 00's e ímpar de 11's, por isso é que F={pi}F = \{pi\}.

Exemplo 2

Queremos verificar se uma palavra constituída por elementos de Σ={x,y,z}\Sigma=\{x,y,z\} acaba em yzyz

Auto 2

D=(Q,Σ,δ,q0,F)Q={<Ei>,<y>,<yz>}Σ={x,y,z}δxyz<Ei><Ei><y><Ei><y><Ei><y><yz><yz><Ei><y><Ei>q0=<Ei>F={<yz>}D = (Q,\Sigma,\delta,q_0,F)\\ Q = \{<Ei>,<y>,<yz>\}\\ \Sigma = \{x,y,z\}\\ \begin{array}{c|c|c|c} \delta & x & y & z \\ \hline <Ei> & <Ei> & <y> & <Ei> \\ \hline <y> & <Ei> & <y> & <yz>\\ \hline <yz> & <Ei> & <y> & <Ei> \end{array}\\ q_0 = <Ei> \\ F = \{<yz>\} \\
Exemplo 3

Queremos um AFD que receba palavras formadas por Σ={a,b,c}\Sigma=\{a,b,c\} e que verifique se começa e acaba na mesma letra.
Neste exemplo, mostra-se apenas a representação gráfica.

Auto 3

F={q1,q2,q3}F = \{q_1,q_2,q_3\}

IMPORTANTE

Podemos definir ainda δ\delta^*, como sendo a função que recebe um estado e uma palavra. Pode ser definida recursivamente como:

δ(q,ϵ)=qqinQ em que ϵΣ eˊ a palavra vaziaδ(q,wa)=δ(δ(q,w),a)qQ,aΣ,wΣΣconjunto das palavras formadas com Σ\delta^*(q,\epsilon) = q \, \forall q in Q \text{ em que } \epsilon \in \Sigma^* \text{ é a palavra vazia}\\ \delta^*(q,wa) = \delta(\delta^*(q,w),a)\\ \forall q \in Q,\quad \forall a \in \Sigma,\quad \forall w \in \Sigma^* \\ \Sigma^* \rightarrow \text{conjunto das palavras formadas com } \Sigma

Aceitação de um AFD

Diz-se que um AFD D=(Q,Σ,δ,q0,F)D = (Q,\Sigma,\delta,q_0,F) aceita a palavra wΣw \in \Sigma^* se δ(q0,w)F\delta^*(q_0,w) \in F (O estado a que chegamos no final pertence aos estados de aceitação)

Linguagem reconhecida

A Linguagem (ou conjunto) reconhecido (ou decidido) pelo AFD D=(Q,Σ,δ,q0,F)D = (Q,\Sigma,\delta,q_0,F) é o conjunto L(D)={wΣ:δ(q0,w)F}L(D) = \{w \in \Sigma^* : \delta^*(q_0,w) \in F\} (conjunto de palavras que o AFD aceita).

Linguagem Regular

Uma Linguagem diz-se Regular se existir um AFD que a reconheça.

Autómato Completo

Até agora, os exemplos vistos foram todos de Autómatos Completos, ou seja, para cada estado temos indicação para mudar de estado para todo o "input" recebido.
Há casos onde isto não acontece, e aí estamos perante um Autómato Não Completo (ANC).

Exemplo Importante - ANC

Queremos um autómato que recebe uma palavra de 00's e 11's e verifica se a palavra é constituída primeiro por um número par de 00's e depois por um número par de 11's. Por exemplo, 0011100111 é aceite, mas 0101101011 não é.

Auto ANC

Seja q0q_0 o estado inicial e F={q1}F=\{q_1\}

Repare-se que não está especificado o que acontece se estivermos em q1q_1 e recebermos um 00, tal como em q3q_3, e em q2q_2 se receber 11.

Não é sem querer que isso acontece apenas nesses casos, de facto nessas situações a palavra seria logo "não aceite".
Nos ANC, omitimos um estado onde vai parar tudo o que não está especificado, o Estado de rejeição.

Auto ANC Comp

NOTA

Para encontrar o complementar do autómato descrito acima, teríamos de incluir o estado omitido, porque é necessário nessa situação.

Autómato Finito Não Determinístico (AFND)

Um AFND é um quíntuplo N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F), onde:

  • QQ é um conjunto finito não vazio
  • q0q_0 é o estado inicial do autómato (q0Q)(q_0 \in Q)
  • Σ\Sigma é um alfabeto (conj. finito de símbolos)
  • FF estados de aceitação/finais (FQ)(F \subseteq Q)
  • δ\delta função que, com o estado atual e com σΣϵ(Σϵ=Σ{ϵ})\sigma \in \Sigma_{\epsilon} (\Sigma_{\epsilon} = \Sigma \cup \{\epsilon\}) que recebe, pode transitar para um conjunto de estados (δ:Q×ΣϵP(Q)(\delta: Q \times \Sigma_{\epsilon} \rightarrow P(Q), onde P(Q)P(Q) é o conjunto dos subconjuntos de Q)Q )

NOTAS

  • Um AFND é feito sabendo que tem de haver pelo menos um caminho para as palavras aceitáveis e nenhum para as que não são.

  • Após aplicar um AFND uma vez, este não classifica uma dada palavra como aceite ou não aceite.

    Caso a palavra seja aceite pelo AFND é aceite, mas se não for, considera-se que pode (ou não) ser.

  • Pode ter mudanças de estado ϵ\epsilon, podem acontecer ou não. (Existe Exemplo mais à frente )

Exemplo 1

AFND para calcular se uma palavra constituída por 00's e 11's tem um 11 na penúltima posição.

Auto ND 1

Este autómato não é completo

N=(Q,Σ,δ,q0,F)Q={q0,q1,q2}Σ={0,1}δ01ϵq0{q0}{q0,q1}q1{q2}{q2}q2q0=q0F={q2}N = (Q,\Sigma,\delta,q_0,F)\\ Q = \{q_0,q_1,q_2\}\\ \Sigma = \{0,1\}\\ \begin{array}{c|c|c|c} \delta & 0 & 1 & \epsilon \\ \hline q_0 & \{q_0\} & \{q_0,q_1\} & \emptyset \\ \hline q_1 & \{q_2\} & \{q_2\} & \emptyset\\ \hline q_2 & \emptyset & \emptyset & \emptyset \end{array}\\ q_0 = q_0 \\ F = \{q_2\} \\

IMPORTANTE

Tal como nos AFD, nos AFND podemos definir ainda δ\delta^*, como sendo a função que recebe um estado e uma palavra e que define a que conjunto de estados podemos acabar no final da palavra. Pode ser definido por:

δ:Q×ΣP(Q)\delta^* : Q \times \Sigma^* \rightarrow P(Q)

Onde:

  • Ao aplicarmos δ\delta^* a um estado qq e se não recebermos nada, poderá transitar para todos as transições ϵ\epsilon do estado qq. Estes estados são representados por E({q})\Epsilon(\{q\}).

    δ(q,ϵ)=E({q}),qQ\delta^*(q,\epsilon) = \Epsilon(\{q\}), \quad \forall q \in Q
  • Ao aplicarmos δ\delta^* a um estado qq quando recebe uma palavra wawa, onde aa é o último símbolo da palavra e wΣw \in \Sigma^*, o estado final será o resultado de aplicar δ\delta, quando recebe a letra aa, a todos os estados a que podemos chegar quando recebemos a palavra ww. Não esquecendo as transições ϵ\epsilon.

δ(q,wa)=rδ(q,w)E(δ(r,a)),r,qQ\delta^*(q,wa) = \bigcup_{r \in \delta^*(q,w)} \Epsilon(\delta(r,a)), \quad \forall r,q \in Q

Aceitação AFND

Diz-se que um N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F) aceita a palavra wΣw \in \Sigma^* se

δ(q0,w)F\delta^*(q_0,w) \cap F \neq \emptyset

Linguagem Reconhecida

A Linguagem Reconhecida por um AFND N=(Q,Σ,δ,q0,F)N=(Q,\Sigma,\delta,q_0,F) será:

L(N)={wΣ:δ(q0,w)F}L(N)=\{w \in \Sigma^* : \delta^*(q_0,w) \cap F \neq \emptyset\}

Teorema 1

Qualquer que seja o AFND DD, existe um AFD NN que lhe é equivalente, ou seja as Linguagens Reconhecidas são iguais. L(N)=L(D)L(N)=L(D)

Passar de AFND para AFD

Exemplo

Temos o seguinte AFND

Auto coisa

Repare-se que temos uma "transição ϵ\epsilon", ou seja, pode acontecer do nada. Deste modo, o estado inicial tanto pode ser q0q_0 ou q2q_2.

Como fazemos para encontrar o AFD?

  1. Cria-se um estado que albergue todos os estados iniciais (neste caso q0q_0 e q1q_1)

  2. Depois, dependendo do input que podemos receber (neste caso aa ou bb) "apontamos" para um novo estado. Se não existir cria-se.
    Atenção: o novo estado, tal como no estado inicial, pode ser um "conjunto de estados"

  3. Se temos nn estados no AFND teremos no máximo 2n2^n no AFD (os vários conjuntos possíveis formados pelos estados do AFND), contudo pode haver estados inúteis (a vermelho abaixo). São estados a que nunca chegamos se partirmos do início. Podem ser omitidos na representação final

Atenção: Não esquecer do estado de rejeição se for necessário (abaixo está a azul)

Segue-se a representação final, com um pequeno exemplo de uma parte da execução abaixo

Auto Coiso 2

  1. Começamos nos estado que engloba os estados iniciais q0q_0 e q2q_2
  2. Quando estamos em q0q_0 ou q2q_2 e recebemos bb, vamos sempre para q1q_1. Se recebermos aa, tanto podemos ir para q0q_0 ou para q1q_1, por causa da transição ϵ\epsilon.
  3. Quando estamos em q2q_2 e recebemos aa, vamos para q0q_0, mas por causa da transição ϵ\epsilon, podemos voltar a q2q_2. Por isso, se recebermos aa em {q0,q2}\{q_0,q_2\} continuamos no mesmo estado.

Repare-se que os estados inúteis (vermelho), nunca são atingidos desde o Ei.

Operações da Esquerda para a Direita - Autómatos

Para fazer uma operação da esquerda para a direita com autómatos (por exemplo: soma, divisão, \dots), basta fazer um autómato que faça a operação da direita para a esquerda e depois trocar as transições e os estados de aceitação com o estado inicial.
Para além disso, também pode ser necessário passar de um AFND para um AFD.

Exemplo 1 - Soma

Vamos definir a soma da esquerda para a direita, com

Σ={[000],[001],[010],[011],[100],,[111],}\Sigma = \{\begin{bmatrix}0\\0\\0\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\0\\0\end{bmatrix}, \dots, \begin{bmatrix}1\\1\\1\end{bmatrix}, \}

Por exemplo,

[010110010110000]<Linguagem reconhecida>\begin{bmatrix} 0&1&0&1&1\\ 0&0&1&0&1\\ 1&0&0&0&0 \end{bmatrix} \in \quad <\text{Linguagem reconhecida}>

Primeira faz-se o autómato da soma da direita para esquerda

Troca 11

Os estados 00 e 11 simbolizam os restos.
q0=0q_0 = 0 e F={0}F = \{0\} (00 é o estado inicial e o de aceitação).

Agora trocamos os estados de aceitação e inicial (como é o mesmo, não trocamos), por isso apenas se trocam as transições entre estados.

Troca 12

Como é um AFD já é o resultado final

Relembrar

As transições não representadas, em ambos, são as transições para o estado de rejeição.

Exemplo 2 - Divisão por 2

Vamos definir a Divisão por 2 da esquerda para a direita, com

Σ={[00],[10],[01],[11],}\Sigma = \{\begin{bmatrix}0\\0\end{bmatrix}, \begin{bmatrix}1\\0\end{bmatrix}, \begin{bmatrix}0\\1\end{bmatrix}, \begin{bmatrix}1\\1\end{bmatrix}, \}

Por exemplo,

[0110100110]<Linguagem reconhecida>\begin{bmatrix} 0&1&1&0&1\\ 0&0&1&1&0 \end{bmatrix} \in \quad <\text{Linguagem reconhecida}>

Primeira faz-se o autómato da Divisão por 2 da direita para esquerda.

Troca 21

Agora, para obtermos a operação da esquerda para a direita fazemos as trocas necessárias.

Troca 22

Agora temos que q0=0q_0=0 e F={q1}F=\{q_1\}.
Temos um AFND. Precisamos de passar para um AFD.

Troca 23

Neste último autómato está representado o estado de rejeição a vermelho

Propriedades

Teorema 2

O complementar de uma Linguagem Regular (LR), a interseção de duas LR e a união de duas LR também são Linguagens Regulares.

Exemplo - Complementação

O seguinte autómato serve para encontrar palavras formadas por x,y,zx,y,z que acabem em yzyz, onde F={<yz>}F=\{<yz>\}.

Auto 2

A única diferença entre este e o seu complementar (palavras que não terminam em yzyz) é o FF, que passa a F={<Ei>,<y>}F=\{<Ei>,<y>\}

Teorema 3

A classe das Linguagens Regulares está fechada para a união, a concatenação e a estrela.

NOTA

Com este Teorema conseguimos construir autómatos maiores/mais complexos, a partir de autómatos mais simples.

União

Sejam A1A_1 e A2A_2 dois autómatos diferentes, cuja representação, omitindo as transições e com estados de aceitação duplamente identificados, é a seguinte:

União 1

Seja L1=L(A1)L_1 = L(A_1) e L2=L(A2)L_2 = L(A_2), (relembrar que L(B)L(B) é a linguagem de aceitação do autómato BB)

L1L2=L(?)L_1 \cup L_2 = L(?)

Para representar o autómato de linguagem reconhecida L1L2L_1 \cup L_2 basta adicionar um novo estado inicial que se liga aos estados inicias de A1A_1 e A2A_2 por transições ϵ\epsilon.

União 2

Esta última representação é de um AFND, para passar para AFD é só aplicar o algoritmo.

Concatenação

Sejam A1A_1 e A2A_2 dois autómatos diferentes, cuja representação, omitindo as transições e com estados de aceitação duplamente identificados, é a seguinte:

União 1

Seja L1=L(A1)L_1 = L(A_1) e L2=L(A2)L_2 = L(A_2),

L1L2=L(?)L1L2={uv:uL1vL2}L_1 \circ L_2 = L(?)\\ L_1 \circ L_2 = \{uv:u \in L_1 \quad \wedge \quad v \in L_2\}

Por exemplo, concatenação de dois autómatos. Um que aceita um número par de 00's e a palavra nula (ϵ)(\epsilon) e outro que aceita um número ímpar de 11's.

L1={ϵ,00,0000,}L2={1,111,11111,}L1L2={1,111,11111,,001,00111,,00001,}L_1 = \{\epsilon,00,0000,\dots\}\\ L_2 = \{1,111,11111,\dots\}\\ L_1 \circ L_2 = \{1,111,11111,\dots,001,00111,\dots,00001,\dots\}

O autómato final aceita apenas uma sequência de 00's à direita e 11's à esquerda, onde há um número par 00's de e ímpar de 11's.


Para representar o autómato de linguagem reconhecida L1L2L_1 \circ L_2 basta adicionar transições ϵ\epsilon, que ligam os estados de aceitação de A1A_1 ao estado inicial de A2A_2.
O estado inicial é o estado inicial de A1A_1 e os de aceitação são os de A2A_2.

Concat 1

Esta representação é de um AFND, para passar para AFD é só aplicar o algoritmo.

Estrela

Seja A1A_1 um autómato, cuja representação, omitindo as transições e com estados de aceitação duplamente identificados, é a seguinte:

Star 1

Seja L1=L(A1)L_1 = L(A_1),

L1=L(?)L1={ϵ}L1(L1L1)=nNL1n,ondeL1nUnia˜o do L n vezesL_1^* = L(?)\\ L_1^* = \{\epsilon\} \cup L_1 \cup (L_1 \circ L_1) \cup \dots\\ = \bigcup_{n \in \N} L_1^n, \quad \text{onde}\\ L_1^n \rightarrow \text{União do L }n\text{ vezes}

Para representar o autómato de linguagem reconhecida L1L_1^* adicionamos um novo estado inicial, que também é de aceitação (para aceitar a palavra nula) e transições ϵ\epsilon como representado abaixo.

Star 2

NOTA

Também podemos chamar Fecho de Kleene à operação Estrela.

Teorema de Kleene

Uma linguagem é regular se e só se pode ser obtida a partir de conjuntos finitos por união, concatenação e/ou estrela.


NOTA

Seja tt uma palavra, t|t| representa o tamanho da palavra


Lema de Pumping

Se L1L_1 é uma linguagem regular, então existe pN1p \in \N_1 tal que toda a palavra sL1s \in L_1 de tamanho sp|s|\geq p, pode ser subdividida em 33 subpalavras, s=xyzs = xyz de tal modo que

  • y>0|y| > 0
  • xyp|xy|\leq p
  • xyyzL1,iN0xyizL1,ondeyirepetir y i vezesxyyz \in L_1, \quad \forall_i \in \N_0 \quad xy^iz \in L_1 ,\quad \text{onde}\\ y^i \rightarrow \text{repetir }y\text{ i vezes}
Demonstração

L1L_1 é uma linguagem regular, onde L1=L(A)L_1=L(A), com A=(Q,Σ,δ,q0,F)A = (Q,\Sigma,\delta,q_0,F).
Seja p=#Qp = \#Q e ss uma palavra de LL, onde s=np|s| = n \geq p.

Quando o autómato AA recebe a palavra ssnn letras e passa por n+1n+1 estados, abaixo encontra-se uma pequena representação desta leitura

q0s1q1s2sirisi+1sjrjsj+1snrnrnFq_0 \rightarrow^{s_1} q_1 \rightarrow^{s_2} \dots \rightarrow^{s_i} r_i \rightarrow^{s_{i+1}} \dots \rightarrow^{s_j} r_j \rightarrow^{s_{j+1}} \dots \rightarrow^{s_n} r_n\\ r_n \in F

Como a palavra s=n|s|=n é maior ou igual ao número de estados, como mencionado, se visita n+1n+1 estados terá de repetir pelo menos um estado (aplicação direta do Princípio de Pombal). Sejam rjr_j a primeira vez que se repete um estado, o estado rir_i.
Podemos dividir a palavra ss em 33 partes: xx, yy e zz, onde s=xyzs=xyz.

  • xx, as primeiras i1i-1 letras da palavra (antes de chegarmos a rir_i)
  • yy, da letra na posição ii até à posição j1j-1 (antes de chegarmos a rjr_j)
  • zz, o resto da palavra a partir da letra na posição jj.

Com esta divisão, retiramos as conclusões finais

  • y>0|y| > 0
  • xyp|xy|\leq p, porque ainda não se repetiu estados
  • xyyzL1,iN0xyizL1,ondeyirepetir y i vezesxyyz \in L_1, \quad \forall_i \in \N_0 \quad xy^iz \in L_1 ,\quad \text{onde}\\ y^i \rightarrow \text{repetir }y\text{ i vezes}
Exemplo - Provar que não é regular

Com o alfabeto Σ={0,1}\Sigma = \{0,1\}, será que existe uma Linguagem Regular LL apenas aceita palavras com 00's à esquerda, 11's à direita, onde existe o mesmo número de 00's e 11's ??

Vamos supor que a linguagem LL é regular e vamos tentar verificar todas as condições do Lema de Pumping:
Como LL é regular tem de existir um pN1p \in \N_1 tal que todas as palavras sLs \in L com tamanho igual ou superior a pp podem ser decompostas em 33 subpalavras (s=xyz)(s = xyz), tais que:

  • y>0|y| > 0
  • xyp|xy|\leq p
  • xyyzL1,iN0xyizL1,ondeyirepetir y i vezesxyyz \in L_1, \quad \forall_i \in \N_0 \quad xy^iz \in L_1 ,\quad \text{onde}\\ y^i \rightarrow \text{repetir }y\text{ }i\text{ vezes}

Se existe um pp que satisfaz as condições acima, então a palavra

s=0p1p=010p111ps=0^p1^p=0_1 \dots 0_p1_1 \dots 1_p

Pertence à linguagem LL e tem de verificar as condições acima, uma vez que s=2pp|s| = 2p \geq p.
Dividindo ss em 33 subpalavras (s=xyz)(s=xyz), pelas condições do Lema de Pumping xyp|xy|\leq p. Deste modo xyxy é uma palavra somente constituída por 00's. (Relembrar que s=0p1ps = 0^p1^p).

Segundo o Lema de Pumping, y>0|y|>0 e xyyzLxyyz \in L, assim, yy terá de ser uma palavra constituída por 00's, MAS quando se repete em xyyzxyyz o número de 00's será maior que o número de 11's, ou seja xyyzLxyyz \notin L.
Chegamos assim a uma Contradição.

Com esta contradição podemos concluir que a linguagem especificada não é regular.