Chiusura con kleene in forma normale di Chomsky - grammatica, grammatica libera dal contesto, stella di kleene, forma normale di Chomsky

Permettere n essere un qualsiasi terminale

Considera la seguente, presumibilmente corretta, rappresentazione della stella kleene finita n:

N → n N | ε

(dove ε è il terminale vuoto).

Wikipedia dice:

Ogni grammatica nella forma normale di Chomsky è libera dal contesto e, al contrario, ogni grammatica libera dal contesto può essere trasformata in una equivalente che si trova nella forma normale di Chomsky.

Non riesco a vedere come la precedente grammatica potrebbe essere trasformata in CNF.

• La grammatica non è libera dal contesto?
• Esiste davvero un modo per rappresentarlo in CNF?

risposte:

Fortunatamente, questo può essere scritto in CNF. Ecco una di queste grammatiche:

S → ε | n | N / A

N → n

A → n | N / A

Pertanto, la lingua è libera dal contesto.

Spero che questo ti aiuti!