Per la prima domanda, vedi testi.

Pedr tutti i linguaggi generabili tramite grammatiche di Chomsky
esiste un algoritmo di semidecisione:
presa una stringa w, si forniscono prima tutte le derivazioni di lunghezza 1 a partire da S,
poi tutte quelle di lunghezza 2, poi tutte quelle di lunghezza 3, e cosi' via.
Se w appartiene al linuaggio, prima o poi neccessariamente la stringa sara' generata.
Se w non appartiene al linguaggio, potremmo andare avanti all'infinito senza
aver mai certezza che essa non possa prima o poi venir generata.<br>
<br>

Per i linguaggi di tipo 1 esiste invece anche un algortmo di decisione.
Le produzioni dei linguaggi di tipo 1 sono, per definizione, della forma

<div align="center">
&alpha; &rarr; &beta;
</div>
con |&alpha;| &le; |&beta;| <br>

Presa una stringa w, si forniscono prima tutte le derivazioni di lunghezza 1 a partire da S,
poi tutte quelle di lunghezza 2, poi tutte quelle di lunghezza 3, e cosi' via.
Se w appartiene al linuaggio, prima o poi neccessariamente la stringa sara' generata,
mentre se non appartiene, dopo un numero finito di passi (che dipende dalla stringa w) potremo esser sicuri che
non verra' mai generata,
poiche' ad ogni passo generiamo stringhe di lunghezza maggiore o uguale a quelle
del passo precedente e poiche' il numero di stringhe di lunghezza fissata e' finito.