TEORÍA DE AUTÓMATAS FINITOS y ANALIZADORES SINTÁCTICOS

UNIVERSIDAD CATÓLICA DE SANTIAGO DEL ESTERO

FACULTAD DE MATEMÁTICA APLICADA

CARRERA: INGENIERÍA EN INFORMÁTICA

Asignatura: LENGUAJES FORMALES Y AUTÓMATAS

Tema: TEORÍA DE AUTÓMATAS FINITOS y ANALIZADORES SINTÁCTICOS

Trabajo Práctico Nº 3                                           

PARTE 1: AUTÓMATAS FINITOS

1. Para el autómata finito definido por la siguiente representación tabular:

1. Dibuje el diagrama de transición.
2. Especifique su definición formal.
3. Defina formalmente el lenguaje que genera y la expresión regular que lo describe.

i) F={q3}

ii) F={q2}

iii) F={q3}

iv) F={q2}

v) F={q2}

vi) F={q0, q3}

2. Obtenga los autómatas finitos correspondientes para los siguientes enunciados. Además:

1. Dibuje el diagrama de transición.
2. Especifique su definición formal.
3. Defina la expresión regular que lo describe.
4. Represente tabularmente la función de transición.

1. Hileras de cero y uno donde después de un cero puede aparecer solamente un uno.
2. Hileras de longitud par compuestas por a o b.
3. El conjunto de hileras sobre el vocabulario {0,1} con tres ceros consecutivos.
4. Hileras de longitud 3 o más compuestas por a o b.
5. Comentarios acotados por |* y *| .
6. Identificadores de cualquier longitud que comiencen con una letra y contengan letras, dígitos y un guión (como mínimo) o ninguno. No puede terminar con un guión.
7. Números fraccionarios con signo, sin ceros no significativos.
8. Números decimales con signo.
9. Números decimales con notación exponencial.

1. Encuentre la expresión regular correspondiente a los siguientes autómatas finitos. Utilice el método de ecuaciones (Lema de Arden: X=AX|B  entonces X=A*B).

PARTE 2: ANALIZADORES SINTACTICOS

4. Analizador Sintáctico Ascendente. Para cada gramática:

4.a. Obtenga la gramática aumentada

4.b. Calcule los conjuntos de primeros y siguientes.

4.c. Realice la colección canónica.

4.d. Construya la tabla.

4.e. Reconozca la hilera dada.

i) S→S+n|S-n|n

Hilera: n-n+n        

ii) S→aSbS|ab

Hilera: aabbab

...