Massimo Caliman
Massimo Caliman
~1 min read

Categories

  • Theoretical Computer Science

Tags

  • Theoretical Computer Science
  • CFG
  • Chomsky
  • Greibach

Languages

  • Italian

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

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