Massimo Caliman
by Massimo Caliman
~1 min read


  • Programming

Kleeneliness is next to Gödeliness


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.


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