1. Determinare e disegnare un automa minimo per il linguaggio denotato dalla seguente espressione regolare:

$$ (ab|bb)^+ $$

Illustrare tutti i passaggi che si sono seguiti per arrivare alla soluzione

• Soluzione

1. Si consideri la seguente grammatica:

$$ S\rarr aSb\space |\space Abb\\ A\rarr bA\space |\space cB\space |\space \epsilon\\ B\rarr cB\space |\space \epsilon $$

1. Scrivere il linguaggio generato dalla grammatica tramite insiemi di stringhe
2. La grammatica è $LL(1)$? Giustificare la risposta
3. Il linguaggio generato dalla grammatica è regolare? Giustificare la risposta

• Soluzione

1. Scrivere una grammatica $LL(1)$ per il seguente linguaggio.

$$ L=\{a^nb^kcc\space |\space n\geq 0, k\geq 0\}\cup\{ba^kc^n\space |\space k>0,n\geq 0\} $$

Dimostrare che la grammatica è effettivamente $LL(1)$

• Soluzione