Kleeneliness is next to Gödeliness

# Chomsky

All productions are of the form A::= BC or A::= σ (σ ∈T and A,B,C ∈N).

Knowing them is important for various reasons, for instance they are used in the proof of correctness of lemma pumping for CF languages.

# Greibach

All productions are of the form A::= σB1…Bn (σ∈T and A,B1,…,Bn ∈N, n≥0).

One of the reasons to know them is that they are used in algorithms to switch from a CFG to a stack automaton (PDA).

If you want to learn about Noam Chomsky and Sheila Greibach you can go to