Deber 14 fundametos de compiladores

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        

• § = 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

• § = 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

• § = Funciones de transición

§ =(A,1) →(B,0)

§=(B,1) →(B,0)

• Pruebas:

Sec. Mínima= 0

Sec. Basica= 01

...