Deber 14 fundametos de compiladores
Enviado por Bernardo Monga • 28 de Febrero de 2023 • Tarea • 268 Palabras (2 Páginas) • 41 Visitas
3) En primer lugar, diseñar reconocedores de estado finito para los conjuntos de secuencias de 1 y 0 descritos a continuación. Despues convierta cada reconocedor en un procesador con un marcador final. Por último, haga que los procesadores detecten las secuencias aceptables e inaceptables tan pronto como sea posible. (First desing finite-state recognizers for the sets of sequences of 1´s and 0´s described below. Then convert each recognizer to a processor with an end-marker. Finally make the processors detect aceptable and unacceptable sequences as son as posible.)
a) El número de 1's es par y el número de 0's es impar.
∑ = Alfabeto de entrada = {0, 1}
• S = Estados = {A, B,}
• S0 = Estado inicial = A
• Diagrama de estados
[pic 1]
• Tabla de Transiciones
0 | 1 | ||
A | B | A | 0 |
B | A | B | 1 |
• § = Funciones de transición
§ =(A,1) →(B,0)
§=(B,0) →(A,1)
• Pruebas:
Sec. Mínima= 0
Sec. Basica= 01
Sec.General= 0101010101
• Expresión Regular: 0*01*|(01*01*01*01*)*
b) Hay un número par de 0´s entre las ocurrencias de un 1.
∑ = Alfabeto de entrada = {0, 1}
• S = Estados = {A, B, C, D}
• S0 = Estado inicial = A
• Diagrama de estados
[pic 2]
• Tabla de Transiciones
0 | 1 | ||
A | D | B | 0 |
B | B | C | 0 |
C | C | A | 0 |
D | C | D | 1 |
• § = Funciones de transición
§ =(A,1) →(B,0)
§=(B,0) →(B,0)
• Pruebas:
Sec. Mínima= 0
Sec. Basica= 01
Sec.General= 0101010101
• Expresión Regular:
c) Hay un número impar de ocurrencias del patrón 00, permitiéndose los solapamientos.
d) Cada ocurrencia del patrón 11 es seguida por un 0.
• Diagrama de estados
[pic 3]
• Tabla de Transiciones
0 | 1 | ||
A | D | B | 0 |
B | C | B | 0 |
C | D | A | 1 |
D | A | D | 1 |
• § = Funciones de transición
§ =(A,1) →(B,0)
§=(B,1) →(B,0)
• Pruebas:
Sec. Mínima= 0
Sec. Basica= 01
...