Aula 6

Todo AFN tem um AFD equivalente. Ou seja, aceita a mesma linguagem.

Prova do Teorema

Seja $N=(Q_n, \Sigma, \delta_n ,q_{0n},F_n)$ o AFN que aceita alguma linguagem $L$. Vamos construir o AFD que ceita $L$.

Caso 1: Sem $\epsilon$-transição

  • $Q_m=P(Q_n)$, ou seja, é o conjunto de $Q_n$.
  • $\Sigma$ é igual nos dois casos.
  • Para cada $R\in Q_n$ e $a \in \Sigma$, seja $\delta(R,a)={q \in Q_n|q\in \delta_n(r,a)\text{ para algum }r\in R}$. Ou seja $\delta_m(R,a)=\displaystyle\bigcup_{r\in R} \delta_n(r,a)$
  • $q_{0m}={q_{0n}}$.
  • $F_m={R\in Q_n|R \text{ contém ao menos 1 estado de aceitação de } Q_n}$ .

Caso 2: Com $\epsilon$-transições

  • $Q_m=P(Q_n)$, ou seja, é o conjunto de $Q_n$.
  • $\Sigma$ é igual nos dois casos.
  • Agora modificamos a função de transição $\delta_n$ trocando $\delta(r,a)$ por $E(\delta(r,a))$. $\delta (R,a)={q\in Q|q\in E(\delta(r,a))\text{ para algum }r\in R}$
  • $q_{0m}={q|q\text{ pode ser alcançada a partir de }R\text{ por zero ou mais } \epsilon \text { transições}}=E({q_{0n}}$. Definimos $E(R)$ como sendo o conjunto de estados que podem ser alcançados a partir de $R$ somente através de $\epsilon$ transições incluindo os membros de $R$
  • $F_m={R\in Q_n|R \text{ contém ao menos 1 estado de aceitação de } Q_n}$ .

Linguagem Regular

Uma linguagem é regular se e somente se existe um AFN que a reconheça.

A linguagem regular é fechada para as operações de união, concatenação e estrela.