¿Convertir la gramática a Chomsky Normal Form?

Question

Convierta la gramática a continuación en la Forma Normal de Chomsky. Da todos los pasos intermedios.

S -> AB | aB 
A -> aab|lambda 
B -> bbA 

Ok así que lo primero que hice fue agregar una nueva variable inicio S0

así que ahora tengo

S0 -> S 
S -> AB | aB 
A -> aab|lambda 
B -> bbA 

entonces me quita todas las reglas lambda:

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

Luego revisé S->S y A->B tipo reglas que no existían Y esa fue la respuesta que se me ocurrió, ¿tengo que hacer algo más o hice algo mal?

Answer 1

Wikipedia dice:

En informática, se dice que una gramática libre de contexto para estar en forma normal de Chomsky si todos sus reglas de producción son de la forma:

• Un -> aC, 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 la cadena vacía. Además, ni B ni C pueden ser el símbolo de inicio.

Continuando su trabajo:

S0 -> S 
S -> AB | aB | B 
A -> aab 
B -> bbA | bb 

En lugar de utilizar | para denotar diferentes opciones, dividido por regla general en varias normas.

S0 -> S 
S -> AB 
S -> aB 
S -> B 
A -> aab 
B -> bbA 
B -> bb 

crear nuevas reglas y Y -> aZ -> b porque vamos a necesitar 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 un 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 

hacer lo mismo para 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, cree C -> YY; para 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, duplicar la regla cuando S ocurre en el lado derecho e inline la regla:

S0 -> B 
S0 -> S 
S -> AB 
S -> YB 
A -> CZ 
C -> YY 
B -> DA 
D -> ZZ 
B -> ZZ 
Y -> a 
Z -> b 

acuerdo con las reglas S0 -> B y S0 -> S uniendo el lado derecho a la izquierda lados de la mano de otras reglas. También, eliminar las reglas de huérfanos (donde el símbolo LHS nunca se usa en el lateral derecho):

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!

Answer 2

respuesta alternativa: La gramática puede producir solamente un número finito de cadenas, a saber 6.

S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb. 

ahora se puede condensar esto de nuevo a Chomsky forma normal con la mano.

---

Por sustitución, podemos encontrar el conjunto de todas las cadenas producidas. Sus reglas iniciales:

S -> AB | aB. 
A -> aab | lambda. 
B -> bbA. 

En primer lugar dividir la regla S:

S -> AB. 
S -> aB. 

Ahora sustituir lo que A y B se expanden en:

S -> AB 
    -> (aab | lambda) bbA 
    -> (aab | lambda) bb (aab | lambda). 
S -> aB 
    -> abbA 
    -> abb (aab | lambda). 

ampliar estos de nuevo para obtener:

S -> aabbbaab. 
S -> aabbb. 
S -> bbaab. 
S -> bb. 
S -> abbaab. 
S -> abb. 

---

Para cambiar este conjunto finito a Chomsky Normal Form, basta hacerlo por fuerza bruta sin ningún factoring inteligente. En primer lugar introducimos dos reglas de terminal:

X -> a. 
Y -> b. 

Ahora, para cada cadena, consumimos la primera letra con una variable terminal y las letras restantes con unas nuevas variables. Por ejemplo, así:

S -> aabbb. (initial rule, not in Chomsky Normal Form) 

S -> XC, where X->a and C->abbb. 
C -> XD, where X->a and D->bbb. 
D -> YE, where Y->b and E->bb. 
E -> YY, where Y->b and Y->b. 

Acabamos de pasar por este proceso para todas las 6 cuerdas, lo que genera una gran cantidad de nuevas variables intermedias.

Answer 3

Sin entrar en demasiada teoría y pruebas (se podía ver esto en Wikipedia), hay algunas cosas que debe hacer cuando se convierte un contexto libre de gramática de Chomsky forma normal, por lo general tiene que realizar cuatro normales-Form Transformaciones. Primero, necesita identificar todas las variables que pueden producir la cadena vacía (lambda/epsilon), directa o indirectamente - (forma libre de Lambda). En segundo lugar, debe eliminar producciones unitarias - (Forma libre de unidades). En tercer lugar, debe encontrar todas las variables que son en vivo/útiles (utilidad). Cuatro, necesitas encontrar todos los símbolos alcanzables (Accesible). En cada paso puede o no tener una nueva gramática. Así que para su problema de esto es lo que me ocurrió ...

---

libre de contexto Gramática

G(Variables = { A B S } 
Start = S 
Alphabet = { a b lamda} 

Production Rules = { 
S -> | AB | aB | 
A -> | aab | lamda | 
B -> | bbA | }) 

Quitar lambda/épsilon

ERRASABLE(G) = { A } 

G(Variables = { A S B } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | B | 
B -> | bbA | bb | }) 

Produtions Retire la unidad

UNIT(A) { A } 
UNIT(B) { B } 
UNIT(S) { B S } 
G (Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Determine live symbol s

LIVE(G) = { b A B S a } 

G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Retire inalcanzable

REACHABLE (G) = { b A B S a } 
G(Variables = { A B S } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | aB | bb | bbA | 
A -> | aab | 
B -> | bbA | bb | }) 

Reemplazar todas las cadenas mixtas con no terminales sólidos Formulario

G(Variables = { A S B R I } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IIA | 
A -> | RRI | 
B -> | IIA | II | 
R -> | a | 
I -> | b | }) 

Chomsky normal

G(Variables = { V A B S R L I Z } 
Start = S 
Alphabet = { a b } 

Production Rules = { 
S -> | AB | RB | II | IV | 
A -> | RL | 
B -> | IZ | II | 
R -> | a | 
I -> | b | 
L -> | RI | 
Z -> | IA | 
V -> | IA | })