logo

Ejemplos de DFA

Ejemplo 1:

Diseñar un FA con ∑ = {0, 1} acepta aquellas cadenas que comienzan con 1 y terminan con 0.

Solución:

programa java sencillo

El FA tendrá un estado inicial q0 a partir del cual solo el flanco con la entrada 1 pasará al siguiente estado.

Ejemplos de autómatas finitos deterministas

En el estado q1, si leemos 1, estaremos en el estado q1, pero si leemos 0 en el estado q1, llegaremos al estado q2 que es el estado final. En el estado q2, si leemos 0 o 1, iremos al estado q2 o al estado q1 respectivamente. Tenga en cuenta que si la entrada termina en 0, estará en el estado final.

Ejemplo 2:

Diseñar un FA con ∑ = {0, 1} acepta la única entrada 101.

Solución:

Ejemplos de autómatas finitos deterministas

En la solución dada, podemos ver que solo se aceptará la entrada 101. Por lo tanto, para la entrada 101, no se muestra otra ruta para otra entrada.

Ejemplo 3:

El diseño FA con ∑ = {0, 1} acepta un número par de ceros y un número par de unos.

Solución:

rudyard kipling si explicación

Este FA considerará cuatro etapas diferentes para la entrada 0 y la entrada 1. Las etapas podrían ser:

Ejemplos de autómatas finitos deterministas

Aquí q0 es un estado inicial y también el estado final. Observe cuidadosamente que se mantiene una simetría de 0 y 1. Podemos asociar significados a cada estado como:

q0: estado de número par de ceros y número par de unos.
q1: estado de número impar de 0 y número par de 1.
q2: estado de número impar de 0 y número impar de 1.
q3: estado de número par de ceros y número impar de unos.

Ejemplo 4:

El diseño FA con ∑ = {0, 1} acepta el conjunto de todas las cadenas con tres ceros consecutivos.

Solución:

Las cadenas que se generarán para este idioma en particular son 000, 0001, 1000, 10001, .... en las que 0 siempre aparece en un grupo de 3. El gráfico de transición es el siguiente:

Ejemplos de autómatas finitos deterministas

Tenga en cuenta que la secuencia de triples ceros se mantiene para llegar al estado final.

Ejemplo 5:

Diseñar un DFA L(M) = {w | w ε {0, 1}*} y W es una cadena que no contiene unos consecutivos.

Solución:

número palíndromo

Cuando ocurren tres 1 consecutivos, el DFA será:

Ejemplos de autómatas finitos deterministas

Aquí son aceptables dos 1 consecutivos o un solo 1, por lo tanto

Ejemplos de autómatas finitos deterministas

Las etapas q0, q1, q2 son los estados finales. El DFA generará las cadenas que no contienen unos consecutivos como 10, 110, 101,..... etc.

Ejemplo 6:

Diseñar un FA con ∑ = {0, 1} acepta las cadenas con un número par de 0 seguidos de un solo 1.

Solución:

El DFA se puede mostrar mediante un diagrama de transición como:

Ejemplos de autómatas finitos deterministas