Dos-manera autómata finito:¿Cómo funciona el autómata recordar el estado

Question

He estado yendo a través de una teoría de autómatas finitos y no entiendo el ejemplo dado, cuando hubo un DFA A = (Q, Σ, δ, q1, F).el 2-DFA B = (Q ∪ Q| ∪ Q|| ∪ {q0, qN, qF}, Σ ∪ {#}, δ|, q0, {qF}) y siguientes idiomas
L = { #u# | uu ∈ L(A)}.

En el siguiente apartado se describirá cómo sería funciona, si estamos leyendo una palabra que pertenece a la lengua.

En el primer procedimiento autómata B de la siguiente manera los estados de Un autómata, cuando se llegue al derecho '#', se detiene, recuerde la aceptación de estado y comienza a moverse de nuevo a través de la copia de estados de Un autómata:Q| como siempre que vienen a la derecha '#'.Después empieza a moverse a través de la copia de los estados Q|| de Un autómata, y una vez que se alcanza el derecho de '#' comprueba si es el salvado la aceptación de estado.La imagen de abajo muestra los movimientos donde qN es una falta/no-aceptación de estado y +1 movimiento de la cabeza a la derecha y -1 movimiento de la cabeza a la izquierda.

Pregunta

¿Cómo funciona el 2-DFA recordar que se llegó durante la primera caminata a través de los estados de Un autómata de la aceptación de estado para la segunda caminata?

Answer 1

Aquí es un simple ejemplo, para NFAs.

Vamos a demostrar que si $L_1,L_2$ son habituales de los idiomas en distintos alfabetos $\Sigma_1,\Sigma_2$, entonces es el siguiente lenguaje de la $\Sigma = \Sigma_1 \cup \Sigma_2$: $$ L = \{ xyz :x,z \in \Sigma_1^*, y \in \Sigma_2^*, xz \en L_1, y \en L_2 \}.$$ Aquí es la idea.Empezar con DFAs $A_1,A_2$ para $L_1,L_2$.Vamos a construir un afd para $L$ que actúa de la siguiente manera.Se inicia mediante la simulación de $A_1$.Cuando se encuentra un símbolo de $\Sigma_2$, se recuerda el estado que $A_1$ es en, y cambia a $A_2$.Cuando se encuentra un símbolo de $\Sigma_1$, cambia de nuevo a $A_1$, suponiendo que $A_2$ es en la aceptación de un estado.Pasa a un estado de error si encuentra una carta de $\Sigma_2$ de nuevo.

Aquí están los detalles, mostrando cómo implementamos recordar el estado de $A_1$.

Vamos $A_1 = \langle Q_1,\Sigma_1,q_{01},\delta_1,F_1 angle$ y vamos a $A_2 = \langle Q_2,\Sigma_2,q_{02},\delta_2,F_2 angle$.Construimos un nuevo DFA $A = \langle Q,\Sigma,q_0,\delta,F angle$ de la siguiente manera:

• El conjunto de estados es $Q = (Q_1 imes \{1\}) \cup (Q_1 imes Q_2) \cup (Q_1 imes \{2\}) \cup \{q_f\}$.Los estados en la primera parte se utiliza para simular $A_1$ antes de que un símbolo de $\Sigma_2$ se ha encontrado.Estados en la segunda parte se utiliza para simular $A_2$ mientras recordando el estado de $A_1$.Los estados en la tercera parte se utiliza para simular $A_1$ después de leer el $y$ parte.El estado final al que se va a manejar diversos modos de fallo.

• El estado inicial es $(q_{01},1)$.

• La transición de la función se define de la siguiente manera:

  • Si $\sigma \en \Sigma_1$ entonces $\delta((p,1),\sigma) = (\delta_1(q,\sigma),1)$:acabamos de antemano $A_1$.
  • Si $\sigma \en \Sigma_2$ entonces $\delta((p,1),\sigma) = (q,\delta_2(q_{02},\sigma))$:nosotros recuerde el estado de $A_1$, y avanzar $A_2$.
  • Si $\sigma \en \Sigma_2$ entonces $\delta((q_1,q_2),\sigma) = (q_1,\delta_2(q_2,\sigma))$:avanzamos $A_2$, mientras que se mantiene el estado de $A_1$ intacto.
  • Si $\sigma \en \Sigma_1$ y $q_2 oen F_2$ entonces $\delta((q_1,q_2),\sigma) = q_f$:el $y$ parte que no está en $L_2$, así que la señal de fracaso.
  • Si $\sigma \en \Sigma_1$ y $q_2 \en F_2$ entonces $\delta((q_1,q_2),\sigma) = (\delta_1(q_1,\sigma),2)$:volvemos a la simulación de $A_1$.
  • Si $\sigma \en \Sigma_1$ entonces $\delta((q_1,2),\sigma) = (\delta_1(q_1,\sigma),2)$:acabamos de antemano $A_1$.
  • Si $\sigma \en \Sigma_2$ entonces $\delta((q_1,2),\sigma) = q_f$:la entrada es incorrecto, así que la señal de fracaso.
  • Para todos $\sigma$, $\delta(q_f,\sigma) = q_f$.
• Los estados finales son $(F_1 imes \{1\}) \cup (F_1 imes F_2) \cup (F_1 imes \{2\})$.La primera parte se encarga del caso $ $ y=z=\epsilon$, el segundo maneja el caso $y eq\epsilon$ y $z=\epsilon$, el tercer maneja el caso $y,z eq \epsilon$.

Esperemos que esto explica cómo un DFA puede cometer una pieza de información en la memoria.Desde un DFA tiene sólo un número finito de estados, que sólo puede almacenar una cantidad constante de información.