Autómatos Finitos

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

Onde $p$ é par, $i$ ímpar e primeiro referimo-nos aos $0$'s e depois aos $1$'s.
"Ei" aponta para o estado inicial.

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

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

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

Queremos um AFD que receba palavras formadas por $\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.

$F = \{q_1,q_2,q_3\}$

Queremos um autómato que recebe uma palavra de $0$'s e $1$'s e verifica se a palavra é constituída primeiro por um número par de $0$'s e depois por um número par de $1$'s. Por exemplo, $00111$ é aceite, mas $01011$ não é.

Seja $q_0$ o estado inicial e $F=\{q_1\}$

Repare-se que não está especificado o que acontece se estivermos em $q_1$ e recebermos um $0$, tal como em $q_3$, e em $q_2$ se receber $1$.

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.

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

Este autómato não é completo

Temos o seguinte AFND

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

Como fazemos para encontrar o AFD?

1. Cria-se um estado que albergue todos os estados iniciais (neste caso $q_0$ e $q_1$)

2. Depois, dependendo do input que podemos receber (neste caso $a$ ou $b$) "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 $n$ estados no AFND teremos no máximo $2^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

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

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

Vamos definir a soma da esquerda para a direita, com

Por exemplo,

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

Os estados $0$ e $1$ simbolizam os restos.
$q_0 = 0$ e $F = \{0\}$ ($0$ é 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.

Como é um AFD já é o resultado final

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

Por exemplo,

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

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

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

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

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

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

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

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

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

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

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

Seja $L_1 = L(A_1)$ e $L_2 = L(A_2)$,

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

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

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

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

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

Seja $L_1 = L(A_1)$,

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

$L_1$ é uma linguagem regular, onde $L_1=L(A)$, com $A = (Q,\Sigma,\delta,q_0,F)$.
Seja $p = \#Q$ e $s$ uma palavra de $L$, onde $|s| = n \geq p$.

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

Como a palavra $|s|=n$ é maior ou igual ao número de estados, como mencionado, se visita $n+1$ estados terá de repetir pelo menos um estado (aplicação direta do Princípio de Pombal). Sejam $r_j$ a primeira vez que se repete um estado, o estado $r_i$.
Podemos dividir a palavra $s$ em $3$ partes: $x$, $y$ e $z$, onde $s=xyz$.

• $x$, as primeiras $i-1$ letras da palavra (antes de chegarmos a $r_i$)
• $y$, da letra na posição $i$ até à posição $j-1$ (antes de chegarmos a $r_j$)
• $z$, o resto da palavra a partir da letra na posição $j$.

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

• $|y| > 0$
• $|xy|\leq p$, porque ainda não se repetiu estados
• $xyyz \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}$

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

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

• $|y| > 0$
• $|xy|\leq p$
• $xyyz \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 $p$ que satisfaz as condições acima, então a palavra

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

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

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