GRAMMATICHE DI TIPO 0

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\to aSBC,CB\to BC,SB\to bF,FB\to bF,$$ $$FC\to cG,GC\to cG,G\to ϵ$$

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

$$S\to aSBC\to abFC\to abcG\to 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

PREVIOUS NEXT