A las siguientes gramáticas llevarlas a la Forma Normal de Greibach, de acuerdo a los siguientes pasos:

a)       limpiar la gramática

b)       eliminar recursividad por izquierda

c)       llevar a la F.N.G.

 Ejercicio 1:

 Resolución:

a) gramática limpia

 b) Regla1:     C:= C1   X:= 1 / 1X

                                    C:= 0 / 0X

c) grupo 3:  B:= A1   B:= CB1 (grupo 2)

                                   B:= 21  B:= 2Y para Y:= 1

    Grupo 2:  B:= CB1   B:= 0B1  B:= 0BY para Y:= 1

                                    B:= 0XB1  B:= 0XBY para Y:= 1

                  A:= CB  A:= 0B

                                 A:= 0XB

 Ejercicio 2:     

Resolución:    

a) gramática limpia

 b) Regla1:     B:= B0   X:= 0 / 0X

                                    B:= 0 / 0X / 1 / 1X

 c) grupo 3:  no hay

    Grupo 2:  A:= B0   A:= 0X0  A:= 0XY para Y:= 0

                                   A:= 00  A:= 0Y

                       A:= 10  A:= 1Y

                                   A:= 1X0  A:= 1XY

                  S:= 0A1  S:= 0AZ para Z:= 1

                  A:= 0A1  A:= 0AZ

  Ejercicio 3:

 Resolución:    

a) gramática limpia

 b)       no hay

 c) grupo 3:    B:= A0   B:= 0A0  B:= 0AY para Y:= 0

                                     B:= 10  B:= 1Y para Y:= 0

  grupo 2:  S:= A0   S:= 0A0  S:= 0AY para Y:=0                                      

S:= 10  S:= 1Y para Y:= 0

                         B:= 1B0  B:= 1BY para Y:= 0

  Ejercicio 4:     

Resolución:    

a) gramática limpia

b)no hay

c) grupo 3:   no hay

Grupo 2:   S:= BC   S:= 0BC

                                   S:= 0C

                                   S:= 1C

                S:= CB  S:= 0CB

                                S:= 0B

                 S:= 0C1  S:= 0CX para X:= 1