Autômatos

Core Concepts

• Alfabeto: $\Sigma$ conjunto finito não vazio de símbolos.
• String: $w$ sequencia finita de símbolos de um $\Sigma$ . representa-se $|w|$ o tamanho da string e $\lambda$ strings vazias/sem símbolos ($|\lambda| = 0$). É uma tupla de símbolos.
• Fecho: $\Sigma^* = \bigcup_{n=0}^{\infty} \Sigma^n$ fechamento de Kleene é o conjunto com todas $w$ existentes em um $\Sigma$.
• Concatenação: operação que forma uma nova palavra a partir da justaposição de duas palavras.
• Substring: uma palavra que aparece em outra. se aparecerem no final é sufixo e se aparecerem no inicio é prefixo.
• Auto-contatenação: $w^i$ recursivamente definida por:
  1. $w^0=\lambda$;
  2. $w^i=w^(i-1)w$ ;
• Reverso: $w^R$ recursivamente definido por:
  1. se $|w|=0$, $w^R=\lambda$;
  2. se $|w|>0$, $w^R=ay^R$ sendo $w=ya$ para algum $a\in\Sigma$ e $y\in\Sigma^*$;
• Linguagem: $L\subseteq\Sigma^*$, exemplo de $L_i$ linguagens formadas a partir do alfabeto binário $\Sigma={0,1}$ e do fecho $\Sigma^*=\{\lambda,0,1,00,01,11,000,001,010,011,...\}$
  • $L_0=\emptyset$
  • $L_1=\lambda$
  • $L_2=\{0,1,00\}$
  • $L_3=$ {$w\in\Sigma^*$ | w é um binário múltiplo de 3}
  • $L_4=\{w\in\Sigma^*|w=01^i,i>=0\}$ // 01, 011, 0111,... como linguagens são string sets podemos aplicar as mesmas operações de strings (concatenação, substring, reverso, auto-concatenação e etc) nas linguagens como um todo. Sejam as languages $L_1=\{ab,1\}$ e $L_2=\{\lambda,b,bb\}$.
  • $L_1L_2=\{ab,abb,abbb,1,1b,1bb\}$
  • $(L_1) ^2=\{abab,ab1,1ab,11\}$
  • $(L_1)^*=\{\lambda,ab,abab,ab1,1ab,11,ababab,abab1,...\}$
  • $(L_1)^+=\{ab,abab,ab1,1ab,11,ababab,abab1,...\}$
• Conjunto Regular: (ou linguagem regular), dado um $\Sigma$, o conjunto que pode ser gerado a partir das operações: união, concatenação e fechamento.
• Regular Expressions: são uma forma simbólica de especificar conjuntos regulares. Conjunto Regular -> Expressão Regular
  • $\{b\}$ -> $b$
  • $\{a,b\}$ -> $a \cup b$
  • $\{ab\}$ -> $ab$
  • $\{a,b\}\{a,b\}=\{aa,ab,ba,bb\}$ -> $(a \cup b)(a \cup b)$
  • $\{a\}^*=\{\lambda, a,aa,aaa,...\}$ -> $a^*$
  • $\{\lambda,a,b,aa,ab,ba,bb,aaa,aab...\}$ -> $(a \cup b)^*$

Autômato Finito - AF

Um AF (ou máquina de estados finito) é um modelo matemático de computação que descreve um máquina abstrata que processa strings de forma sequencial (símbolo a símbolo) e unidirecional (como uma fita de leitura).
ela é composta por:

• Fita de Leitura Unidirecional
• Controle + Função de Transição
• Registrador de Estado Atual

Um autômato reconhece uma linguagem se a última transição resultar em um estado final.

AF Determinístico - AFD

$M = (E, \Sigma, \delta, i, F)$.

• $M$: AFD.
• $E$: conjunto finito de estados.
• $\delta: E \times \Sigma \to E$: função de transição. ($\delta$ é uma função total).
• $i \in E$: é o estado inicial.
• $F \subseteq E$: são os estados finais.

Para toda linguagem finita existe um AFD.

Propriedades

• Cada $(e, s) \in E \times \Sigma$ leva a um único outro $E$, não há "escolha própria" (se tiver em um estado e lendo um certo símbolo SEMPRE levará ao mesmo estado). É um autômato determinista.
• Todos os pares $(e, s) \in E \times \Sigma$ são mapeados para um outro estado. A função $\delta$ é total.
• Existe apenas um único estado inicial $i$. E exitem um conjunto $F$ finito de estados finais.

Linguagem de um AFD

$L(M)=\{w \in \Sigma^* \mid [i, w] \vdash^* [f, \lambda] \text{, } \exists f \in F \}$. Ou seja, $L$ é um conjunto de palavras $w$ que a partir de uma sequência de transições de estados chega-se na configuração $[f, \lambda]$, ou seja, todos os símbolos são processados e o estado atual é um dos finais. Em resumo, um conjunto de palavras que o autômato aceita/reconhece. Dizemos que dois AFDs são equivalentes quando ambos reconhecem a mesma linguagem.

Determinismo: Completo vs Incompleto

Se $\delta$ é total, dizemos que o determinismo é completo. Se $\delta$ é parcial, dizemos que o determinismo é parcial. No exemplo acima, $M_1 \equiv M_2$ pois ambos reconhecem a mesma linguagem $(ab)^*c$. No entanto, a diferença entre eles é que dada uma palavra inválida (como, $aaaaaaaaa$) $M_1$ iria ler todos os $a's$ até chegar na configuração $[e, \lambda] \mid e \notin F$ (mais precisamente $e = Error$), rejeitando a string. Já $M_2$ determinista incompleto iria produzia uma parada HALT imediatamente ao ler o segundo $a$ da palavra, rejeitando naquele momento mesmo.

Produto de AFDs

É a simulação de dois AFDs em paralelo. Seja $M_1=(E_1,\Sigma,\delta_1, i_1,F_1)$ e $M_2=(E_2,\Sigma,\delta_2, i_2,F_2)$ pode-se construir $M_3=(E_3,\Sigma,\delta_3, i_3,F_3)$ em que:

• $E_3 = E_1 \times E_2$
• $i_3 = (i_1, i_2)$
• $\delta_3((e_1,e_2), a) = (\delta_1(e_1,a),\delta_2(e_2,a)), \forall e_1 \in E_1, e_2 \in E_2, a \in \Sigma$

$$F_3 = \begin{cases} F_1 \times F_2 & L(M_3) = L(M_1) \cap L(M_2) \\ (F_1 \times E_2) \cup (E_1 \times F_2) & L(M_3) = L(M_1) \cup L(M_2) \end{cases}$$

Dessa forma, ao executar-se dois AFDs os estados finais que definem se a linguagem $L(M_3)$ do AFD produzido será:

• INTERSECÇÃO, $L(M_3)=L(M_1) \cap L(M_2)$, se $F_3=F_1 \times F_2 =\{(pz, pu)\}$. (Ou seja, $L(M_3)$ seria as palavras que possuem # pares de 1 E # pares de 0).
• UNIÃO, $L(M_3)=L(M_1) \cup L(M_2)$, se $F_3=(F_1 \times E_2) \cup (E_1 \times F_2)=\{(pz, pu), (pz, iu), (iz, pu)\}$. (Ou seja, $L(M_3)$ seria as palavras que possuem # pares de 1 OU # pares de 0).

AF Não Determinístico - AFN

$M = (E, \Sigma, \delta, i, F)$.

• $\delta: E \times \Sigma \to \mathcal{P}(E)$: função de transição. ($\mathcal{P}(E)$ é o power set de $E$).

Uma palavra pode gerar diferentes computações.

Se existir alguma computação de $w$ que resulta na configuração $[e, \lambda] \mid e \in F$ significa que $w \in L(M)$.

AF Não Determinístico com Transição $\lambda$ - AFN-$\lambda$

$M = (E, \Sigma, \delta, i, F)$.

• $\delta: E \times (\Sigma \cup \{\lambda\}) \to \mathcal{P}(E)$: função de transição. A transição $\lambda$ (ou vazia) é aquela realizada sem a necessidade de nenhum símbolo de entrada.

Equivalência entre AFs

Autômatos são equivalentes se reconhecem a mesma linguagem.

Função Fecho lambda - $f\lambda$

Conjunto de todos os estados que podem ser alcançados a partir do mesmo sem a leitura de nenhum símbolo de entrada.

Conversões de AFs

Converter um AF em outro equivalente é mudar a computação mas manter a linguagem aceita.

AFN-$\lambda$ ⟶ AFN

• AFN-$\lambda$: $M = (E, \Sigma, \delta, i, F)$;
• AFN: $M' = (E, \Sigma, \delta', i, F')$;

$$\delta'(e_i,a)=\bigcup_{r \in f\lambda(e_i)}f\lambda(\delta(r,a)), \forall e_i \in E, \forall a \in \Sigma$$ $$F' = \begin{cases} F \cup \{i\} & \text{, if } f \lambda(i) \cap F \neq \emptyset \\ F & \text{, else} \end{cases}$$

AFN ⟶ AFD

---

• AFN: $M = (E, \Sigma, \delta, i, F)$;
• AFD: $M' = (E', \Sigma, \delta', i', F')$;

$$E'=\mathcal{P}(E)$$ $$i'=\{i\}$$ $$F'=\{R \in E' \mid R \cap F \neq \emptyset\}$$ $$\delta'(R,a)=\bigcup_{r \in R}\delta(r,a), \forall R \in E', \forall a \in \Sigma$$

Referências

---