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:
- Construir um AFN
que reconheça a linguagem . - Construir um AFN
que reconheça a linguagem . - Usar transição
(epsilon) para construir um AFN que reconheça (concatenação de com ). - Gerar o AFD equivalente ao AFN
.
Informações relevantes dadas:
- Alfabeto implícito:
. - Podemos usar transição
(epsilon) para ligar a . - As linguagens
e incluem a cadeia vazia (pois o operador permite zero repetições).
Passo 2
Construção do AFN
que reconhece
.
Explicação didática rápida do raciocínio:
-
são repetições de : vazio, , , … - 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
e depois voltar ao inicial ao consumir o .
Definição formal de
:
com
todas as outras transições vazias,
Comentário prático:
é final para aceitar
. Um
leva para
; um
em
volta para
, fechando um bloco
.
Exemplo de aceitação: para
,
-
e é de aceitação.
Passo 3
Construção do AFN
que reconhece
.
Raciocínio semelhante: repetições de
: vazio,
,
, …
Definição formal de
:
com
todas as outras transições vazias,
Comentário:
é final para aceitar
. Um
leva para
; um
em
volta para
, fechando um bloco
.
Passo 4
Construção do AFN
que reconhece
por concatenação com
-transição.
Raciocínio didático:
- Para concatenar duas linguagens reconhecidas por AFNs, basta ligar cada estado de aceitação de
por ao estado inicial de ; os estados de aceitação finais do novo AFN são os de . - Aqui
tem único estado de aceitação ; tem único estado de aceitação . Então adicionamos -transição de para .
Definição formal de
:
com
transições (não listadas as vazias):
e a
-transição de concatenação
Os estados de aceitação são os de
:
Verificação rápida por exemplo:
- A cadeia vazia
é aceita: (aceita vazio) (aceita vazio), é final. - A cadeia
aceita: e é final. - A cadeia
aceita: .
Passo 5
Explicação do método de determinização (construção do subconjunto) com
-fechos.
Conceitos necessários e fórmula:
-
-fecho (epsilon-closure) de um conjunto de estados , denotado , é o conjunto de estados alcançáveis a partir de usando apenas transições (inclui próprio). - Para cada conjunto de estados
do AFN, a transição do AFD em símbolo é:
e depois tomamos o
-fecho:
- Estado inicial do AFD:
. - Estados de aceitação do AFD: todos os subconjuntos que contêm pelo menos um estado de aceitação do AFN (
aqui).
Calculamos os
-fechos dos estados singulares no nosso AFN
:
-
porque existe . -
(nenhuma saindo de ). -
. -
.
Passo 6
Construção passo a passo dos estados do AFD (subconjuntos) e transições.
Estado inicial do AFD:
Agora aplicamos
+
para cada símbolo
e
, e para cada novo subconjunto gerado.
- A partir de
:
- Em
:
Então
com
.
- Em
:
Então
com
.
- A partir de
:
- Em
: Chamar este conjunto vazio de . - Em
:
Então
.
- A partir de
:
- Em
:
Então
com
.
- Em
:
- A partir de
:
- Em
: - Em
:
- Estado vazio
:
- Em
e permanece .
Resumo dos subconjuntos (nomes que usaremos):
Estados de aceitação do AFD: aqueles que contém
, ou seja
e
.
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:
Definição final do AFD:
com
Passo 8
Observações finais e checagem rápida:
- O AFD reconhece
porque qualquer leitura começa em (que corresponde estar no início de um bloco ou de um bloco por conta da -ligação) e as transições previstas fazem os ciclos corretos: para consumir blocos e para consumir blocos . Estados de aceitação permitem a cadeia vazia e completas repetições no final.
Resposta
AFD equivalente