Práctica 1

Autómatas, Gramáticas y Lenguajes

Elena Gaudioso Vázquez y Tomás García Saiz

Introducción

La práctica tendrá una ponderación del 15 % de la nota definitiva de laasignatura, siempre que se obtenga una nota superior o iguala 5 puntos en laprueba presencial.

La práctica sólo podrá entregarse utilizando la aplicaciónde Tareas de loscursos virtuales. La entrega de la misma será un archivo comprimido, en formato*.zip, nombrado como “Apellido1 Apellido2, Nombre (DNI).zip”. El archivocomprimido deberá contener un archivo *.jff, que es el resultado del programaJFLAP, por cada uno de los ejercicios que componen la práctica. Cada archivo*.jff debe nombrarse como “NombreApellido1_ej<numejercicio>”.jff donde<numejercicio>será el número del ejercicio que corresponda (1,2,3,4,5,6,7,8,9o 10). Cualquier práctica que no se entregue siguiendo estasinstrucciones seráconsiderada “NO APTA” y evaluada con una nota de 0 puntos.

Cada uno de los ejercicios de la práctica será evaluado con una notacomprendida entre {0..1}. Si el autómata entregado no está correctamente definidoserá evaluado con un cero. Para la evaluación de cada autómata correctamentedefinido se utilizará un juego de pruebas y la nota será proporcional al número depruebas que superen correctamente.

Debemos recordar al alumnado que las prácticas son personales, por lo tanto,está completamente prohibido la entrega por múltiples alumnos de la mismapráctica. En el caso de detectarse dos o más prácticas iguales, ambas prácticasserán consideradas “NO APTA” y evaluadas con una nota de 0 puntos. Además,se informará al vicerrectorado de alumnos.

Autómatas finitos

Ejercicio 1

Dado el alfabetoΣ = {x, y, z}, construir un autómata finito determinista quesolamente reconozca todas las palabras que cumplan las siguientes condiciones:

Número dex ∈ [0 . . . 2]

Número dey = 3*x +2, dondex es el número dex’s presentes en unadeterminada cadena.

Ejercicio 2

Dado el alfabetoΣ = {(, ), {, }, [, ]}, construir un autómata que solamentereconozca todas las palabras de 4 letras con los paréntesis,corchetes y llaves

1

correctamente escritos. Es decir, por cada paréntesis, llave o corchete abierto debehaber uno cerrado adecuadamente.

Ejercicio 3

Construir el autómata finito con cuatros estados que reconozco el lenguajecuya expresión regular es:

(ab∗ ∪ ba∗)∗ (ba∗ ∪ ab∗)

Ejercicio 4

Construir el autómata finito que reconozca el lenguaje generado por lasiguiente gramática:

1. S → aA

2. A → b

3. A → bA

4. A → bS

5. A → aB

6. S → bB

7. B → a

8. B → aB

9. B → aS

10. B → bA

Ejercicio 5

Dado el lenguaje L representado por la gramática siguiente.Construir unautómata finito determinista que reconozca el lenguajeL′ = L − λ.

1. S → λ

2. S → aS

3. S → bS

4. S → aA

5. S → bB

6. A → λ

7. A → bA

8. A → aS

9. A → aB

10. B → λ

11. B → aB

12. B → bS

13. B → bA

2

Autómatas a Pila

Ejercicio 6

Dado el alfabetoΣ = {x, y, z}, construir un autómata a pila con 6 estados, omenos, que reconozca el lenguaje formado por todas las palabras que cumplen lassiguientes condiciones:

Número dex ∈ [0 . . . 2]

Número dey = 3*x +2 dondex es el número dex’s de la palabra

Nota: Se permite introducir múltiples elementos en la pila en cadatransición.

Nota 2: Utizaremos el símbolo “#” para indicar al autómata que se haterminado la entrada, por lo tanto siempre será el último elemento de la entrada,y el autómata no tendrá en cuenta todo lo que venga a continuación de dichosímbolo.

Ejercicio 7

Dado el alfabetoΣ = {a, b, c}, construir un autómata a pila que compruebe sidos cadenas consecutivas de cinco letras cada una, son iguales.

Ejercicio 8

Construir el autómata a pila que reconozca el lenguaje generado por lasiguiente gramática:

1. S → ACCS

2. S → BSCC

3. S → CC

4. A → a

5. B → b

6. C → c

3

Ejercicio 9

Para definir el lenguaje de este ejercicio vamos a utilizar elconcepto sílaba.Vamos a definir una sílaba, como cualquier combinación posible de 4 elementosdel alfabeto. Además, vamos a definir una palabra válida del lenguaje, como laconcatenación de cualquier cantidad de sílabas válidas.

Pedimos construir un autómata a pila que compruebe para cadacadena deentrada:

1. Que la palabra pertenezca al lenguaje.

2. Que la palabra contenga exactamente 4 sílabas.

3. Que la primera y la tercera sílaba , o que la segunda y la cuarta sílaba formenun palíndromo.

El alfabeto del lenguaje esΣ = {a, b, c}.

Ejercicio 10

Construir un autómata a pila determinista que reconozca el lenguaje definidopor la siguiente gramática:

1. S → SS

2. S → xy

3. S → yx

4. S → xyS

5. S → yxS

6. S → xSy

7. S → ySx

8. S → Sxy

9. S → Syx

4