Massimo Caliman
by Massimo Caliman
~1 min read

Categories

  • Programming

Tags

  • Context-Free Grammar

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

  1. https://en.wikipedia.org/wiki/Noam_Chomsky
  2. https://en.wikipedia.org/wiki/Sheila_Greibach