Kleeneliness is next to Gödeliness

Chomsky

Tutte le produzioni sono della forma A::= BC oppure A::= σ (σ ∈ T e A,B,C ∈N).

Conoscerle è importante per vari motidi, per esempio sono utilizzate nella prova di correttezza del pumping lemma per i linguaggi CF.

Greibach

Tutte le produzioni sono della forma A::= σB1…Bn (σ ∈ T e A,B1,…,Bn ∈N, n≥0).

Uno dei motivi per conoscerle è che sono utilizzate negli algoritmi che permettono di passare da una CFG ad un automa a pila (PDA).

Se volete approndire qualcosa Noam Chomsky e Sheila Greibach potete andare su