Skip to main content
  1. Linguaggi_modelli_computazionalis/

Grammatiche di tipo 0

·112 words·1 min· ·
Table of Contents
Linguaggi e modelli computazionali - This article is part of a series.
Part 4: This Article

Sono grammatiche prive di restrizioni sulle produzioni, e ammessa la produzione della stringa vuota (ergo le frasi possono ridursi di lunghezza)

Un possibile esempio e il seguente:

$$ S \rightarrow aSBC, \space CB \rightarrow BC, \space SB \rightarrow bF, \space FB \rightarrow bF, $$

$$ FC \rightarrow cG, \space GC \rightarrow cG, \space G \rightarrow \epsilon $$

Notare che tale linguaggio ammette produzioni in cui la frase viene accorciata

$$ S \rightarrow aSBC\rightarrow abFC \rightarrow abcG \rightarrow abc $$

Rami di derivazione morti
#

Nelle grammatiche di Tipo 0 è possibile arrivare a una stringa in cui non è possibile applicare altre produzioni, in questo caso si parla di ramo di derivazione morto

Matteo Longhi
Author
Matteo Longhi
I’m a software engineer with a passion for Music, food, dogs, videogames and open source software, i’m currently working as a devops engineer
Linguaggi e modelli computazionali - This article is part of a series.
Part 4: This Article