Ejercicios para AFD, AFN

Ejercicios para AFD, AFN, y expresiones regulares, genera los siguientes productos :

1. AFD
2. Tabla de definición de AFD
3. Conjunto de primeros 20 palabras LEXICOGRÁFICAMENTE 
4. AFN con cadena vacía
5. AFN  con cadena de longitud mayor a 0
6. AFN con más de una transición de un mismo símbolo
7. Expresión regular para el lenguaje generado por el AFD

de los siguientes lenguajes :

1. Las cadenas que terminan con 1, con el alfabeto {0,1}
2. Las cadenas que terminan en 11, con el alfabeto {0,1}
3. Construir un autómata finito que reconozca los números múltiplos de 3. La entrada será en binario empezando por el dígito más significativo. La  entrada tendrá tamaño indefinido, y puede empezar por ceros.
4. En algunos lenguajes de programación, los comentarios aparecen entre los
   delimitadores “/*” y “*/” como marca inicial y final del comentario. Sea L el lenguaje de todas las cadenas de comentarios delimitados. Así pues todo elemento de L, empieza por /* y acaba por */, pero no debe tener ningún */ intermedio. Por simplicidad consideraremos que el alfabeto sería {a, b, /,*}. Indicar el Autómata Finito Determinista que reconoce L.

1.- AFD:

2.- Definición AFD:

Un autómata finito no determinista (abreviado AFND) es un autómata finito que, a diferencia de los autómatas finitos deterministas (AFD), posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

En un AFND puede darse cualquier de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada. Considérese una modificación al modelo del autómata finito para permitirle ninguna, una o más transiciones de un estado sobre el mismo símbolo de entrada.

3.- Conjunto de primeros 20 palabras LEXICOGRÁFICAMENTE.

Consideremos el alfabeto Σ = {a, b}

•Orden lexicográfico: ε, a, b, aa, ab, ba, bb, aaa, ...

{a,b,aa,ab,ba,abb,aab,aaa,aba,bbb.bba.baa,bab,aaaa,aaab,aabb,abaa,aaba,abab,abab,bbbb,baaa,bbaa,bbba,baba,abab}

4.- AFN con cadena vacía

[pic 1]

5.- AFN con cadena de longitud mayor a 0

[pic 2]

1. Las cadenas que terminan con 1, con el alfabeto {0,1}

L={1, 01, 11, 001, 101, 111, 0001, 0101, 0111, 1111}

1. Las cadenas que terminan en 11, con el alfabeto {0,1}

L={11, 011, 0011, 00011,000011}

1. Construir un autómata finito que reconozca los números múltiplos de 3. La entrada será en binario empezando por el dígito más significativo. La  entrada tendrá tamaño indefinido, y puede empezar por ceros.

[pic 3]

1. En algunos lenguajes de programación, los comentarios aparecen entre los
   delimitadores “/*” y “*/” como marca inicial y final del comentario. Sea L el lenguaje de todas las cadenas de comentarios delimitados. Así pues todo elemento de L, empieza por /* y acaba por */, pero no debe tener ningún */ intermedio. Por simplicidad consideraremos que el alfabeto sería {a, b, /,*}. Indicar el Autómata Finito Determinista que reconoce L.

 [pic 4]

...