TEORÍA DE AUTÓMATAS FINITOS y ANALIZADORES SINTÁCTICOS
Enviado por juanma88 • 7 de Junio de 2016 • Práctica o problema • 607 Palabras (3 Páginas) • 174 Visitas
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:
- Dibuje el diagrama de transición.
- Especifique su definición formal.
- Defina formalmente el lenguaje que genera y la expresión regular que lo describe.
i) F={q3}
f | 1 | 2 | 3 |
q1 | q1 | q1 | q2 |
q2 | q3 | q3 | q3 |
q3 | q3 | q3 | q3 |
ii) F={q2}
f | a | b |
q0 | q1 | q2 |
q1 | q2 | q1 |
q2 | q2 | q2 |
iii) F={q3}
f | a | b | c | d |
q0 | q1 | |||
q1 | q1 | q2 | ||
q2 | q3 | |||
q3 | q3 |
iv) F={q2}
f | 0 | 1 |
q0 | q0 | q1 |
q1 | q0 | q2 |
q2 | q0 | q2 |
v) F={q2}
f | a | b | c |
q0 | q1 | q3 | |
q1 | q2 | ||
q2 | q2 | q2 | |
q3 | q2 |
vi) F={q0, q3}
f | 0 | 1 |
q0 | q0 | q1 |
q1 | q1 | q2 |
q2 | q2 | q3 |
q3 | q3 |
2. Obtenga los autómatas finitos correspondientes para los siguientes enunciados. Además:
- Dibuje el diagrama de transición.
- Especifique su definición formal.
- Defina la expresión regular que lo describe.
- Represente tabularmente la función de transición.
- Hileras de cero y uno donde después de un cero puede aparecer solamente un uno.
- Hileras de longitud par compuestas por a o b.
- El conjunto de hileras sobre el vocabulario {0,1} con tres ceros consecutivos.
- Hileras de longitud 3 o más compuestas por a o b.
- Comentarios acotados por |* y *| .
- 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.
- Números fraccionarios con signo, sin ceros no significativos.
- Números decimales con signo.
- Números decimales con notación exponencial.
- 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).
i) | ii) |
ii) | iv) |
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
...