Problema de construcción de la NFA

Question

Necesito construir un autómata que reconozca el siguiente lenguaje de cadenas sobre el alfabeto $\{a,b\}$ : El conjunto de todas las cadenas sobre alfabeto $\{a,b\}$ con la subsecuencia $abba$ . (Una subsecuencia es como una subcadena, salvo que no tiene que tener caracteres consecutivos. Por ejemplo, $abaaba$ y $babbbba$ están en el idioma).

Answer 1

Su NFA acepta todas las cadenas de más de $\{a,b\}$ que tengan una longitud mínima de 3. Por ejemplo, $aaa$ está en la lengua reconocida por ella, al igual que $bbbbbbbbab$ . Observe que se le pide no determinista autómata finito, por lo que debe hacer uso de esto. El único requisito para nuestro lenguaje es que contenga como mínimo un $a$ dos $b$ y otro $a$ en ese orden.

Así que hagamos un NFA que diga todo $a$ y $b$ y luego de forma no determinista supone que el $a$ que queremos está llegando. Luego, hacemos lo mismo con los dos $b$ y el último $a$ . Tal NFA puede parecerse a éste.

Obsérvese que el $a$ y $b$ 's que exigimos a nuestra cadena son claramente discernibles en la NFA. En $\varepsilon$ -las transiciones deben concebirse como adivinando de forma no determinista que el $a$ o $b$ que buscamos aparece en el siguiente símbolo que leemos. Si no es así, entonces esta rama no determinista falla, pero entonces otra rama no determinista pasará, siempre y cuando la cadena esté en nuestro lenguaje.

---

Como ejemplo, veamos la cadena $bababa$ . En el estado inicial, dividimos de forma no determinista en dos ramas, una que toma el $b$ -transición y una que toma la $\varepsilon$ -transición:

1) $\rightarrow b$

2) $\rightarrow \varepsilon$

A continuación, vemos que la rama 2) no puede aceptar la primera $b$ por lo que esta rama muere. El siguiente símbolo es un $a$ así que nos bifurcamos de nuevo, una rama toma el $a$ -transición y el otro toma la $\varepsilon$ -transición, y esta vez el $\varepsilon$ -rama puede realmente tomar el $a$ -transición:

1) $\rightarrow b \rightarrow a$

2) $\rightarrow \varepsilon \not \rightarrow$

3) $\rightarrow b \rightarrow \varepsilon \rightarrow a$

El siguiente símbolo de la cadena es $b$ así que nos bifurcamos de nuevo (¡muchas veces!):

1) $\rightarrow b \rightarrow a \rightarrow b$

2) $\rightarrow \varepsilon \not \rightarrow$

3) $\rightarrow b \rightarrow \varepsilon \rightarrow a \rightarrow b$

4) $\rightarrow b \rightarrow \varepsilon \rightarrow a \rightarrow \varepsilon$

5) $\rightarrow b \rightarrow a \rightarrow \varepsilon$

Vemos que la rama 4) puede aceptar la $b$ por lo que ésta continúa, mientras que la rama $5)$ sólo puede aceptar un $a$ así que éste muere. Este proceso de ramificación continúa, y si completas el ejemplo, encontrarás que una de las ramas eventualmente alcanzará el estado de aceptación.

Como puedes ver, obtenemos muchas ramas, y puedes pensar en cada una de las $\varepsilon$ -ramas como la NFA adivinando de forma no determinista que el símbolo actual es el símbolo que buscamos. Como se puede ver en el ejemplo, si esta suposición es incorrecta, la rama simplemente morirá, y entonces la NFA hará nuevas suposiciones hasta que adivine correctamente o no queden más símbolos en la cadena.

Answer 2

Así que esto funcionó, pero me pregunto cuál es la diferencia entre éste y el de MRP.