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.
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:
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:
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:
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á:
Aquí son aceptables dos 1 consecutivos o un solo 1, por lo tanto
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: