Esta interseção de DFAs está correta?

Estou construindo um autômato finito determinístico (DFA) para um idioma de todas as strings definidas sobre cujo comprimento é par e o número de s é ímpar. Eu construí cada DFA separadamente e depois combinei: $\{0,1\}$ $1$

dfas e sua união

O procedimento fornecido para combinar DFAs está correto?
EDIT: Originalmente escreveu união; realmente fazendo o cruzamento.
Será que alguém sugerir materiais na construção DFAs
dadas restrições à duração e número de s ou s? $0$ $1$

De acordo com o link fornecido por Merbs, desenvolvi esta FA. insira a descrição da imagem aqui
Esta FA não aceita um idioma de tamanho uniforme.

automata regular-languages finite-automata Rafay Zia Mir
fonte

Sua abordagem parece correta, mas você deve usar a interseção e não a união dos dois DFAs.

A.Schulz

Aprendi apenas três métodos, como união de FAs, concatenação de FAs e encerramento de FAs. Estou procurando, mas não consigo encontrar a interseção de FAs. Você pode me indicar algum link útil?

Rafay Zia Mir

Em uma pesquisa no Google: este site é bom, mas o essencial é que você faça a interseção dos estados que aceitam.

Merbs

Eu visitei este link, mas isso fornece um exemplo específico, não uma regra, bcz, quando encontramos uma FA difícil, seria difícil construir uma interseção.

Rafay Zia Mir

Dado dois DFAs com e estados, a construção de um DFA com estados (com cada estado representando um par de estados nos DFA originais) é a regra; e, em seguida, você pode minimizar o DFA resultante por meio de um conjunto de procedimentos (principalmente heurísticos?).

m

$m$

n

$n$

m n

$mn$

Merbs

Respostas:

Sim, isso é chamado de produtos Constuction - dada DFAs e , podemos construir : $M_1$ $M_2$ $M=M_1\times M_2$

$M$ consiste em pares de estados de seus DFAs constituintes; portanto, se os DFAs originais tiverem estados e , o produto seria . $A,B,C$ $x,y,z$ $\{Ax,Ay,Az,Bx,By,Bz,Cx,Cy,Cz\}$
A função de transição é atualizada para que, em uma etapa específica, uma string faça com que a transição do estado para e para a transição de para , o produto faça a transição de para $M_1$ $A$ $B$ $M_2$ $x$ $y$ $Ax$ $By$
O estado inicial é o par que consiste nos estados iniciais dos DFAs constituintes (ou seja, ). $Ax$
Se nós estamos construindo o DFA que determina se ambos dos dois DFAs constituintes aceitaria a corda, então a estados aceitar de é a interseção (os pares formados por aceitar estados de ambos). Se estivermos construindo o DFA que determina se um dos dois DFAs constituintes aceitaria a sequência, os estados de aceitação de são a união (aqueles pares constituídos por estados de aceitação de qualquer um). No seu exemplo, e são os estados de aceitar e ; a interseção seria $M$
$M$
$x_1$ $y_0$ $M_1$ $M_2$ $\{x_1y_0\}$ enquanto a união seria . $\{x_1y_0,x_1y_1,x_0y_0\}$

Incluí alguns outros DFAs sobre restrições de comprimento para referência.

exemplo dfas

Merbs
fonte

Em casos de união, o conjunto de estados aceitantes não deve ser ? (Não que alguém usaria essa construção para união; casos, estados são suficientes em oposição a essa construção produz. Pelo menos se estivermos falando de NFA.)

M_{1} Q_{2} \cup Q_{1} M_{2}

$M_1Q_2 \cup Q_1M_2$

| Q_{1} | + | Q_{2} | + 1

$|Q_1|+|Q_2|+1$

| Q_{1} | | Q_{2} |

$|Q_1||Q_2|$

Raphael

@Raphael, seu comentário, embora correto, foi complicado o suficiente para que eu não entendesse sem pensar mais, por isso tentei "separar o tamanho" dele. Se você quiser editar minha resposta para incluir uma discussão sobre os NFAs, crie um wiki da comunidade (ou adicione sua própria resposta).

Merbs

@ Merbs, obrigado por sua ajuda e resposta. Desculpe pela resposta tardia, mas eu tentei esse método para outras FA e isso foi bem-sucedido.

Rafay Zia Mir

OK, "leigos" um pouco. Pegue os e . Considere o DFA , em que é definido por: a ideia é que o estado de registra os estados em que e seria se eles processados a corda separadamente. aceita apenas se os dois aceitarem. $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ $M = (Q_1 \times Q_2, \Sigma, \delta, (q_1, q_2), F_1 \times F_2)$ $\delta$

δ ((q^{'}, q^{″}), a) = (δ_{1} (q^{'}, a), δ_{2} (q^{″}, a))

$\delta((q', q''), a) = (\delta_1(q', a), \delta_2(q'', a))$

M

$M$

M_{1}

$M_1$

M_{2}

$M_2$

M

$M$

vonbrand
fonte

Não tenho certeza de que maneira isso é "leigos"; esta é a definição formal (correta) para a construção do produto. Você deve mencionar como o conjunto de estados de pode ser reduzido em muitos casos; ninguém quer desenhar toda essa porcaria.

M

$M$

Raphael