1. Si consideri la seguente espressione regolare:

$$ (a|aa|ab)^*|(aaa|ab)^+ $$

Determinare un automa minimo che accetta il linguaggio denotato dall’espressione (giustificare i passaggi)

• Soluzione 🟢

1. Si consideri la seguente grammatica

$$ S\rightarrow Sab\space |\space bA\\ A\rightarrow cA\space |\space b $$

• Si scriva il linguaggio generato come insieme di stringhe.
• La grammatica è LR(1)?. Se si, si dia la tabella di un parser shift-reduce bottom-up e si esegua il parsing della stringa bb. Giustificare la propria risposta facendo vedere tutti i passi che sono stati seguiti per arrivare alla stessa.
• Soluzione 🟢

1. Si consideri il seguente linguaggio

$$ L=\{p^nqr^k\space |\space n\geq 0,k>0\}\cup\{q^ns^m\space |\space n>0,m\geq 0\} $$

• Definire una grammatica LL(1) per il linguaggio, mostrando tutti i passaggi.

• Dare una definizione dalla sintassi (SDD) associata alla grammatica data che calcoli, per il simbolo iniziale, un attributo $v$ intero uguale alla somma tra:

  • la differenza tra il numero di $p$ e il numero di $q$ e
  • la differenza tra il numero di $s$ e il numero di $q$

  nella stringa data. Ad esempio, per la stringa $ppqr$ si ha $v=(2-1)+(0-1)=1-1=0$. Per la stringa $qqqss$ si ha $v=(0-3)+(2-3)=-3-1=-4$

• Soluzione 🟢