La traducción de una gramática recursiva a la derecha en Chomsky Forma Normal

Question

Estoy tratando de hacer un ejercicio en el que traduzco una gramática en la forma normal de Chomsky. Entiendo cómo hacer esto en circunstancias normales, pero esta vez la gramática estoy trabajando con recursiva es correcto. (Técnicamente, la gramática es la respuesta a la pregunta anterior, por lo que sólo podría tener la gamma mal.)

creo que puedo hacer esto mediante el uso de una secuencia fija de reglas en lugar de reglas varepsilon pero quiero asegurarme de que no estoy yendo en la dirección equivocada. Es más fácil de explicar con un ejemplo:

Para una gramática que produce n 'aes donde n es mayor que 0 y un múltiplo de tres: (no se preocupe, esto es completamente diferente a la gramática mi ejercicio real)

S-> Aaaa
A-> Aaaa
A-> ε

¿Podría ser la traducción correcta:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

A pesar de que su gramática es recursiva derecha, puede realizar la transformación Chomsky forma normal como lo haría cualquier otra gramática (no recursiva derecha). Sólo tiene que seguir el algoritmo descrito en su libro, que probablemente consta de dos pasos: (1) reemplazar todas las apariciones de terminales a por reglas a -> a , donde Un no se produce en el conjunto de reglas; (2) transformar todas las reglas A -.> W , donde len (w)> 2, por las reglas de longitud 2 que contiene variables frescas

Para su regla, entonces, construir una regla para los terminales que se derivan, dicen K -> a , y reemplazar todas las ocurrencias de la terminal de a

A -> AKKK

A continuación, poner en la gramática CNF

A    -> AA'
A'   -> KA''
A''  -> KK