Massimo Caliman
Massimo Caliman
~1 min read

Categories

  • Theoretical Computer Science

Tags

  • PDA
  • CF
  • CFG

Languages

  • Italian

Kleeneliness is next to Gödeliness

Un linguaggio L 1 non può essere riconosciuto deterministicamente per pila vuota 2 se esistono due stringhe distinte di L tali che una è prefisso dell’altra.

In termini più formali se ∃ u,v ∈ L : u è prefisso di v dove il concetto, di prefisso può essere ulteriormente formalizzato come v = ux dove x è una stringa dell’alfabeto a cui appartengono entrambe le stringhe u e v.

L’utilità di questa proprietà è evidente in quanto ci permette di capire se stiamo perdendo del tempo cercando di sviluppare un parser elementare utilizzando un PDA per un dato linguaggio che contiene stringhe del tipo aabb e aabbbb, l’automa si fermerà, per pila vuota, appena consumato il prefisso.

  1. La dimostrazione sarà riportata in un prossimo post. 

  2. Quindi da un automa a pila (PDA)