Construa o AFN M1 que reconhecer a linguagens (ab)* e AFN M2 que reconhecer a linguagens (ba), em seguida use a transição lambda para construir o AFN M que reconhece a linguagens (ab)(ba)*. Gere o AFD equivalente.

Passo 1

O enunciado pede três coisas, em sequência:
  1. Construir um AFN M_1 que reconheça a linguagem (ab)^*.
  2. Construir um AFN M_2 que reconheça a linguagem (ba)^*.
  3. Usar transição \lambda (epsilon) para construir um AFN M que reconheça (ab)^*(ba)^* (concatenação de M_1 com M_2).
  4. Gerar o AFD equivalente ao AFN M.
Informações relevantes dadas:
  • Alfabeto implícito: \Sigma=\{a,b\}.
  • Podemos usar transição \lambda (epsilon) para ligar M_1 a M_2.
  • As linguagens (ab)^* e (ba)^* incluem a cadeia vazia \lambda (pois o operador * permite zero repetições).

Passo 2

Construção do AFN M_1 que reconhece (ab)^*.
Explicação didática rápida do raciocínio:
  • (ab)^* são repetições de ab: vazio, ab, abab, …
  • Um AFN simples com dois estados em loop consegue isso: um estado inicial que também é de aceitação (para aceitar a cadeia vazia) e um estado intermediário para consumir o a e depois voltar ao inicial ao consumir o b.
Definição formal de M_1:
M_1 = (Q_1,\Sigma,\delta_1,q_0^1,F_1)
com
Q_1 = \{q_0^1,q_1^1\},\quad \Sigma=\{a,b\},
\delta_1(q_0^1,a)=\{q_1^1\},\quad \delta_1(q_1^1,b)=\{q_0^1\},
todas as outras transições vazias,
q_0^1 \text{ é o estado inicial, }\quad F_1=\{q_0^1\}.é
Comentário prático: q_0^1 é final para aceitar \lambda. Um a leva para q_1^1; um b em q_1^1 volta para q_0^1, fechando um bloco ab.
Exemplo de aceitação: para w=abab,
  • q_0^1 \xrightarrow{a} q_1^1 \xrightarrow{b} q_0^1 \xrightarrow{a} q_1^1 \xrightarrow{b} q_0^1 e q_0^1 é de aceitação.

Passo 3

Construção do AFN M_2 que reconhece (ba)^*.
Raciocínio semelhante: repetições de ba: vazio, ba, baba, …
Definição formal de M_2:
M_2 = (Q_2,\Sigma,\delta_2,q_0^2,F_2)
com
Q_2 = \{q_0^2,q_1^2\},\quad \Sigma=\{a,b\},
\delta_2(q_0^2,b)=\{q_1^2\},\quad \delta_2(q_1^2,a)=\{q_0^2\},
todas as outras transições vazias,
q_0^2 \text{ é o estado inicial, }\quad F_2=\{q_0^2\}.é
Comentário: q_0^2 é final para aceitar \lambda. Um b leva para q_1^2; um a em q_1^2 volta para q_0^2, fechando um bloco ba.

Passo 4

Construção do AFN M que reconhece (ab)^*(ba)^* por concatenação com \lambda-transição.
Raciocínio didático:
  • Para concatenar duas linguagens reconhecidas por AFNs, basta ligar cada estado de aceitação de M_1 por \lambda ao estado inicial de M_2; os estados de aceitação finais do novo AFN são os de M_2.
  • Aqui M_1 tem único estado de aceitação q_0^1; M_2 tem único estado de aceitação q_0^2. Então adicionamos \lambda-transição de q_0^1 para q_0^2.
Definição formal de M:
M=(Q,\Sigma,\delta,q_{start},F)
com
Q = Q_1 \cup Q_2 = \{q_0^1,q_1^1,q_0^2,q_1^2\},
\Sigma=\{a,b\},\quad q_{start} = q_0^1,
transições (não listadas as vazias):
\delta(q_0^1,a)=\{q_1^1\},\quad \delta(q_1^1,b)=\{q_0^1\},
\delta(q_0^2,b)=\{q_1^2\},\quad \delta(q_1^2,a)=\{q_0^2\},
e a \lambda-transição de concatenação
\delta(q_0^1,\lambda)=\{q_0^2\}.
Os estados de aceitação são os de M_2:
F=\{q_0^2\}.
Verificação rápida por exemplo:
  • A cadeia vazia \lambda é aceita: q_0^1 (aceita (ab)^* vazio) \xrightarrow{\lambda} q_0^2 (aceita (ba)^* vazio), q_0^2 é final.
  • A cadeia ab aceita: q_0^1\xrightarrow{a}q_1^1\xrightarrow{b}q_0^1\xrightarrow{\lambda}q_0^2 e q_0^2 é final.
  • A cadeia ba aceita: q_0^1\xrightarrow{\lambda}q_0^2\xrightarrow{b}q_1^2\xrightarrow{a}q_0^2.

Passo 5

Explicação do método de determinização (construção do subconjunto) com \lambda-fechos.
Conceitos necessários e fórmula:
  • \lambda-fecho (epsilon-closure) de um conjunto de estados T, denotado \mathrm{EpsClos}(T), é o conjunto de estados alcançáveis a partir de T usando apenas transições \lambda (inclui T próprio).
  • Para cada conjunto de estados S do AFN, a transição do AFD em símbolo x\in\Sigma é:
\mathrm{move}(S,x)=\bigcup_{p\in S}\delta(p,x),
e depois tomamos o \lambda-fecho:
\delta_{DFA}(S,x)=\mathrm{EpsClos}(\mathrm{move}(S,x)).
  • Estado inicial do AFD: \mathrm{EpsClos}(\{q_{start}\}).
  • Estados de aceitação do AFD: todos os subconjuntos que contêm pelo menos um estado de aceitação do AFN ( q_0^2 aqui).
Calculamos os \lambda-fechos dos estados singulares no nosso AFN M:
  • \mathrm{EpsClos}(\{q_0^1\})=\{q_0^1,q_0^2\} porque existe \delta(q_0^1,\lambda)=\{q_0^2\}.
  • \mathrm{EpsClos}(\{q_1^1\})=\{q_1^1\} (nenhuma \lambda saindo de q_1^1).
  • \mathrm{EpsClos}(\{q_0^2\})=\{q_0^2\}.
  • \mathrm{EpsClos}(\{q_1^2\})=\{q_1^2\}.

Passo 6

Construção passo a passo dos estados do AFD (subconjuntos) e transições.
Estado inicial do AFD:
S_0 = \mathrm{EpsClos}(\{q_0^1\}) = \{q_0^1,q_0^2\}.
S_0 é estado de aceitação pois contém q_0^2.
Agora aplicamos \mathrm{move} + \mathrm{EpsClos} para cada símbolo a e b, e para cada novo subconjunto gerado.
  1. A partir de S_0=\{q_0^1,q_0^2\}:
  • Em a: \mathrm{move}(S_0,a)=\delta(q_0^1,a)\cup\delta(q_0^2,a)=\{q_1^1\}\cup\varnothing=\{q_1^1\}.
\mathrm{EpsClos}(\{q_1^1\})=\{q_1^1\}.
Então S_0 \xrightarrow{a} S_1 com S_1=\{q_1^1\}.
  • Em b: \mathrm{move}(S_0,b)=\delta(q_0^1,b)\cup\delta(q_0^2,b)=\varnothing\cup\{q_1^2\}=\{q_1^2\}.
\mathrm{EpsClos}(\{q_1^2\})=\{q_1^2\}.
Então S_0 \xrightarrow{b} S_2 com S_2=\{q_1^2\}.
  1. A partir de S_1=\{q_1^1\}:
  • Em a: \mathrm{move}(S_1,a)=\delta(q_1^1,a)=\varnothing,\quad \mathrm{EpsClos}(\varnothing)=\varnothing.Chamar este conjunto vazio de S_\varnothing.
  • Em b: \mathrm{move}(S_1,b)=\delta(q_1^1,b)=\{q_0^1\},
\mathrm{EpsClos}(\{q_0^1\})=\{q_0^1,q_0^2\}=S_0.
Então S_1 \xrightarrow{b} S_0.
  1. A partir de S_2=\{q_1^2\}:
  • Em a: \mathrm{move}(S_2,a)=\delta(q_1^2,a)=\{q_0^2\},
\mathrm{EpsClos}(\{q_0^2\})=\{q_0^2\}.
Então S_2 \xrightarrow{a} S_3 com S_3=\{q_0^2\}.
  • Em b: \mathrm{move}(S_2,b)=\delta(q_1^2,b)=\varnothing \Rightarrow S_\varnothing.
  1. A partir de S_3=\{q_0^2\}:
  • Em a: \mathrm{move}(S_3,a)=\delta(q_0^2,a)=\varnothing \Rightarrow S_\varnothing.
  • Em b: \mathrm{move}(S_3,b)=\delta(q_0^2,b)=\{q_1^2\}=S_2.
  1. Estado vazio S_\varnothing=\varnothing:
  • Em a e b permanece S_\varnothing.
Resumo dos subconjuntos (nomes que usaremos):
S_0=\{q_0^1,q_0^2\},\quad S_1=\{q_1^1\},\quad S_2=\{q_1^2\},\quad S_3=\{q_0^2\},\quad S_\varnothing=\varnothing.
Estados de aceitação do AFD: aqueles que contém q_0^2, ou seja S_0 e S_3.

Passo 7

Tabela de transição do AFD (resultado da construção por subconjuntos).
Apresento a tabela de transição com as setas já calculadas:
\begin{array}{c|cc} \text{Estado AFD} & a & b \\\ \hline S_0=\{q_0^1,q_0^2\} & S_1=\{q_1^1\} & S_2=\{q_1^2\} \\\ S_1=\{q_1^1\} & S_\varnothing=\varnothing & S_0=\{q_0^1,q_0^2\} \\\ S_2=\{q_1^2\} & S_3=\{q_0^2\} & S_\varnothing=\varnothing \\\ S_3=\{q_0^2\} & S_\varnothing=\varnothing & S_2=\{q_1^2\} \\\ S_\varnothing=\varnothing & S_\varnothing & S_\varnothing \end{array}
Definição final do AFD:
D=(Q_D,\Sigma,\delta_D,S_0,F_D)
com
Q_D=\{S_0,S_1,S_2,S_3,S_\varnothing\},
\Sigma=\{a,b\},\quad S_0\text{ é o estado inicial},é
F_D=\{S_0,S_3\}.

Passo 8

Observações finais e checagem rápida:
  • O AFD reconhece (ab)^*(ba)^* porque qualquer leitura começa em S_0 (que corresponde estar no início de um bloco ab ou de um bloco ba por conta da \lambda-ligação) e as transições previstas fazem os ciclos corretos: S_0\xrightarrow{a}S_1\xrightarrow{b}S_0 para consumir blocos ab e S_0\xrightarrow{b}S_2\xrightarrow{a}S_3\xrightarrow{b}S_2 para consumir blocos ba. Estados de aceitação permitem a cadeia vazia e completas repetições no final.

Resposta

M_1=(\{q_0^1,q_1^1\},\{a,b\},\delta_1,q_0^1,\{q_0^1\}) com \delta_1(q_0^1,a)=\{q_1^1\}, \delta_1(q_1^1,b)=\{q_0^1\} (outras transições vazias).\n
M_2=(\{q_0^2,q_1^2\},\{a,b\},\delta_2,q_0^2,\{q_0^2\}) com \delta_2(q_0^2,b)=\{q_1^2\}, \delta_2(q_1^2,a)=\{q_0^2\} (outras transições vazias). \n
M=(\{q_0^1,q_1^1,q_0^2,q_1^2\},\{a,b\},\delta,q_0^1,\{q_0^2\}) com \delta(q_0^1,a)=\{q_1^1\}, \delta(q_1^1,b)=\{q_0^1\}, \delta(q_0^2,b)=\{q_1^2\}, \delta(q_1^2,a)=\{q_0^2\} e \delta(q_0^1,\lambda)=\{q_0^2\}. \n
AFD equivalente D=(Q_D,\{a,b\},\delta_D,S_0,F_D) com Q_D=\{S_0,S_1,S_2,S_3,S_\varnothing\}, S_0=\{q_0^1,q_0^2\} (inicial), S_1=\{q_1^1\}, S_2=\{q_1^2\}, S_3=\{q_0^2\}, S_\varnothing=\varnothing, F_D=\{S_0,S_3\}, e transições:\n
\;S_0\xrightarrow{a}S_1,\;S_0\xrightarrow{b}S_2,\n
\;S_1\xrightarrow{a}S_\varnothing,\;S_1\xrightarrow{b}S_0,\n
\;S_2\xrightarrow{a}S_3,\;S_2\xrightarrow{b}S_\varnothing,\n
\;S_3\xrightarrow{a}S_\varnothing,\;S_3\xrightarrow{b}S_2,\n
\;S_\varnothing\xrightarrow{a}S_\varnothing,\;S_\varnothing\xrightarrow{b}S_\varnothing.

Exercícios relacionados