Conversión a la forma normal de Chomsky

Question

Estoy tratando de aprender a convertir cualquier gramática libre de contexto a la Forma Normal de Chomsky. En el ejemplo de abajo, traté de aplicar la lógica de la Forma Normal de Chomsky, para dar lugar a una gramática, donde cada símbolo produce dos símbolos, o cada símbolo produce una terminal.

No estoy 100% seguro de que mi implementación sea correcta, y es importante que entienda cómo hacerlo, agradecería que alguien me dijera si estoy en el camino correcto.

Gramática sin contexto

S -> ASA | aB
A -> B | S
B -> b | epsilon

Después de convertir a:

Forma normal de Chomsky

S-> CA | CB
C -> AS | a | S
B -> b | epsilon

Muchas gracias de antemano.

Answer 1

Conversión de la Gramática Libre de Contexto a la Forma Normal de Chomsky : (Te diré los pasos y también resolveré el ejemplo que has pedido simultáneamente)

Paso 1 : Introducir un nuevo no-terminal $S_0$ y hacer que derive la variable de inicio que es S

Así,

$S_0$ -> S

S -> ASA | aB

A -> B | S

B -> b | $\varepsilon$

Paso 2 : Eliminar todos los $\varepsilon$ transiciones

Así que tenemos que eliminar B -> $\varepsilon$

Para ello debemos sustituir B por $\varepsilon$ en el lado derecho de cada producción que tenga B

Así tenemos,

$S_0$ -> S

S -> ASA | aB | a

A -> B | S | $\varepsilon$

B -> b

Ahora nuevo $\varepsilon$ se introduce una transición que es A -> $\varepsilon$ por lo que también hay que eliminarlo

$S_0$ -> S

S -> ASA | aB | a | SA | AS | S ... Nota: S -> S puede ser ignorado

A -> B | S

B -> b

Paso 3: Eliminar todas las transiciones unitarias, es decir, aquellas producciones que tienen exactamente un no-terminal en el lado derecho.

por lo que tenemos que eliminar A -> B , A->S , $S_0$ -> S

Por lo tanto, primero quitando A-> B

$S_0$ -> S

S -> ASA | aB | a | SA | AS

A -> b | S

B -> b

NOw quitando A-> S

$S_0$ -> S

S -> ASA | aB | a | SA | AS

A -> b | ASA | aB | a | SA | AS

B -> b

NOw quitando $S_0$ -> S

$S_0$ -> ASA | aB | a | SA | AS

S -> ASA | aB | a | SA | AS

A -> b | ASA | aB | a | SA | AS

B -> b

Paso 4 : Ahora elimina todas las producciones que no están en CNF

$S_0$ -> AM | NB | a | SA | AS

S -> AM | NB | a | SA | AS

A -> b | AM | NB | a | SA | AS

B -> b

M -> SA

N-> a

La CFG anterior está en CNF .

)