Encontramos la contestación a esta dificultad, o por lo menos eso deseamos. Si tienes alguna inquietud puedes escribirlo en el apartado de preguntas, que con placer te ayudaremos
Solución:
Existe una forma sistemática de crear autómatas para la intersección de lenguajes. Sean $A$ y $B$ los autómatas de entrada. Los estados del nuevo autómata serán todos los pares de estados de $A$ y $B$, es decir $S_Acap B = S_A times S_B$, el estado inicial será $i_A cap B = langle i_A, i_B rangle$, donde $i_A$ y $i_B$ son los estados iniciales de $A$ y $B$, y $F_Acap B = F_A times F_B$ donde $F_X$ denota el conjunto de estados de aceptación de $X$. Finalmente, la función de transición $delta_A cap B$ se define de la siguiente manera para cualquier letra $alpha in Sigma$ y establece $p_1, p_2 in S_A$, $q_1, q_2 in S_B$:
$$ langle p_1, q_1 rangle xrightarrow[A cap B] alpha langle p_2, q_2 rangle quad text si quad p_1 xrightarrow[A] alpha p_2 quad texty quad q_1 xrightarrow[B] alpha q_2 $$
Tenga en cuenta que dicho autómata generalmente no es mínimo (por ejemplo, la intersección podría ser solo un idioma vacío). También podría ser útil (pero no es necesario) hacer que los autómatas de entrada sean mínimos ya que la salida es de tamaño cuadrático.
Espero que ayude 😉
En el primer y segundo autómata, puede unir los estados “0” y “2”. Los autómatas son correctos, pero no mínimos.
En el tercer autómata, las flechas $00 to 01$ y $01 to 12$ no tienen etiqueta. Además, parece que no aceptará “abcbc”.
sdcvvc ya ha notado algunos problemas con su solución, y dtldarek ha dado un enfoque sistemático a tales problemas. Sugeriré cómo podría simplemente haber creado el DFA deseado desde cero en este caso relativamente simple.
Si desea crear el DFA desde cero, debe asegurarse de que cada $a$ esté seguido inmediatamente por un $b$. y cada $c$ está inmediatamente precedido por un $b$. En cada estado, por lo tanto, necesita saber dos cosas: ¿fue la última entrada un $a$ (porque entonces el siguiente deber ser un $b$), y la última entrada fue un $b$ (por lo que la siguiente podría ser un $c$). Esto sugiere que debería comenzar con cuatro estados, digamos $s_0,s_a,s_b$ y $s_c$, con la idea de que estoy en el estado
$$beginalign* &s_0text inicialmente,\ &s_atext si la última entrada fue a,\ &s_btext si la última entrada fue b,text y\ &s_ctext si la última entrada fue c;. endalign*$$
¿Qué transiciones necesito entonces?
Si estoy en $s_a$, la única entrada aceptable es $b$, entonces quiero $s_astackrelblongrightarrow s_b$; con su convención no hay transiciones $s$ o $c$ fuera de $s_a$. (Tendría un estado no aceptador de ‘volcado’ $s_d$ con transiciones $s_dstackrela,b,clongrightarrow s_d$ y luego tendría transiciones $s_astackrelalongrightarrow s_d$ y $s_a stackrelclongrightarrow s_d$.)
Si estoy en $s_b$, todas las entradas son aceptables y necesito las transiciones $s_bstackrelalongrightarrow s_a$, $s_bstackrelblongrightarrow s_b$ y $s_bstackrelc longrightarrow s_c$.
Si estoy en $s_c$, solo se buscan $s_cstackrelalongrightarrow s_a$ y $s_cstackrelblongrightarrow s_b$: $c$ es una entrada inaceptable.
Finalmente, si estoy en $s_0$, solo se buscan $s_0stackrelalongrightarrow s_a$ y $s_0stackrelblongrightarrow s_b$: $c$ es una entrada inaceptable. Evidentemente, puedo combinar $s_0$ y $s_c$ en un solo estado, al que llamaré $s_c$. La tabla de transición para el DFA resultante es:
$$beginarrayc &a&b&c\ hline s_a&&s_b&\ s_b&s_a&s_b&s_c\ s_c&s_a&s_b\ endarray$$
Una nota sobre la construcción descrita por dtldarek: debe pensar en ella como una forma de hacer que un DFA imite dos simultáneamente. Cuando estás en el estado $s$ en el primer autómata y en el estado $t$ en el segundo, estás en el estado $langle s,trangle$ en el nuevo. Las transiciones en el nuevo autómata imitan las del primer autómata en la forma en que tratan la primera coordenada de estado, e imitan las del segundo autómata en la forma en que tratan la segunda coordenada de estado. Es una construcción muy útil. Suponga que tiene DFA que aceptan los idiomas $L_1$ y $L_2$. Dependiendo de cómo elija los estados del aceptador, puede usar esta construcción para obtener un DFA que acepte $L_1cap L_2$ (como en este problema), un DFA que acepte $L_1cup L_2$ o un DFA que acepte $L_1setminus L_2$.
Al final de la página puedes encontrar las anotaciones de otros sys admins, tú todavía eres capaz dejar el tuyo si lo crees conveniente.