Lucián, miembro de este staff, nos hizo el favor de escribir este artículo ya que controla perfectamente este tema.
Solución:
Wikipedia dice:
En informática, se dice que una gramática libre de contexto está en la forma normal de Chomsky si todas sus reglas de producción tienen la forma:
- A -> antes de Cristo, o
- A -> α, o
- S -> ε
donde A, B, C son símbolos no terminales, α es un símbolo terminal, S es el símbolo de inicio y ε es el vacío string. Además, tampoco B ni C puede ser el símbolo de inicio.
Continuando con su trabajo:
S0 -> S S -> AB | aB | B A -> aab B -> bbA | bb
En lugar de usar | para denotar diferentes opciones, divida una regla en varias reglas.
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb
Crea nuevas reglas Y -> a y Z -> b porque los necesitaremos pronto.
S0 -> S S -> AB S -> aB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
S -> aB no es de la forma S -> BC porque a es una terminal. Así que cambia a en Y:
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> bb Y -> a Z -> b
Haz lo mismo con el B -> bb regla:
S0 -> S S -> AB S -> YB S -> B A -> aab B -> bbA B -> ZZ Y -> a Z -> b
Para A -> aab, crear C -> YY; por B -> bbA, crear D -> ZZ:
S0 -> S S -> AB S -> YB S -> B A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
Para S -> B, duplica la única regla donde S ocurre en el lado derecho e inserta la regla:
S0 -> B S0 -> S S -> AB S -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
Lidiar con las reglas S0 -> B y S0 -> S uniendo el lado derecho al lado izquierdo de otras reglas. Además, elimine las reglas huérfanas (donde el símbolo LHS nunca se usa en RHS):
S0 -> DA S0 -> ZZ S0 -> AB S0 -> YB A -> CZ C -> YY B -> DA D -> ZZ B -> ZZ Y -> a Z -> b
Y hemos terminado. ¡Uf!
Sin entrar en demasiada teoría y pruebas (puede ver esto en Wikipedia), hay algunas cosas que debe hacer al convertir una gramática libre de contexto a la forma normal de Chomsky, generalmente debe realizar cuatro transformaciones de forma normal. Primero, necesita identificar todas las variables que pueden producir el vacío string(lambda / epsilon), directa o indirectamente – (forma sin lambda). En segundo lugar, debe eliminar las producciones unitarias (forma sin unidades). En tercer lugar, debe encontrar todas las variables activas / útiles (utilidad). Cuatro, debe encontrar todos los símbolos alcanzables (Accesible). En cada paso, es posible que tenga o no una nueva gramática. Entonces, para tu problema, esto es lo que se me ocurrió …
Gramática libre de contexto
G(Variables = A B S
Start = S
Alphabet = a b lamda
Production Rules =
A -> )
Eliminar lambda / épsilon
ERRASABLE(G) = A
G(Variables = A S B
Start = S
Alphabet = a b
Production Rules = AB )
Eliminar las producciones de la unidad
UNIT(A) A
UNIT(B) B
UNIT(S) B S
G (Variables = A B S
Start = S
Alphabet = a b
Production Rules =
A -> )
Determinar símbolos en vivo
LIVE(G) = b A B S a
G(Variables = A B S
Start = S
Alphabet = a b
Production Rules =
S -> )
Quitar inalcanzable
REACHABLE (G) = b A B S a
G(Variables = A B S
Start = S
Alphabet = a b
Production Rules = )
Reemplaza todo mixed cadenas con no terminales sólidos
G( Variables = A S B R I
Start = S
Alphabet = a b
Production Rules =
B -> )
Forma normal de Chomsky
G( Variables = V A B S R L I Z
Start = S
Alphabet = a b
Production Rules =
I -> )
Si estás de acuerdo, eres capaz de dejar una división acerca de qué te ha impresionado de este enunciado.