Si consideri il seguente automa:

image.png

  1. Si scriva il linguaggio accettato dall’automa tramite una espressione regolare
  2. Si dia un automa minimo che accetti lo stesso linguaggio dell’automa dato. Si mostrino tutti i passaggi che sono stati seguiti per arrivare alla soluzione

Si consideri la seguente grammatica:

$$ S\rarr aSb\space |\space Ac\\ A\rarr bA\space |\space B\\ B\rarr aBc\space |\space \epsilon $$

  1. Scrivere formalmente il linguaggio generato dalla grammatica come insieme di stringhe.
  2. Si dica se esiste, per la grammatica, un parser deterministico predittivo top-down o un parser deterministico bottom-up. Si giustifichino le risposte

Si consideri un linguaggio di stringhe di parentesi tonde e quadrate bilanciate non interlacciate, cioè tali che per ogni parentesi di un certo tipo aperta ce n’è una corrispondente chiusa e il tipo di ogni parentesi che si chiude corrisponde al tipo dell’ultima parentesi aperta che non ha ancora una parentesi chiusa corrispondente. Le stringhe di parentesi bilanciate non interlacciate possono concatenarsi una dopo l’altra. La stringa vuota è da considerarsi una stringa di parentesi bilanciate non interlacciata

Ad esempio: , (), [], (()()), ([()]), (()())([()]) sono stringhe di parentesi bilanciate non interlacciate. Si noti che la stringa (()()) contiene due parentesi tonde concatenate all’interno delle parentesi tonde più esterne. Si noti anche che la stringa (()())([()]) e composta dalla concatenazione delle due stringhe (()()) e ([()]). Si noti inoltre che la stringa ([()]) appartiene al linguaggio poiché ogni parentesi che si chiude e del tipo dell’ultima parentesi aperta non ancora chiusa. Infine, si noti che la stringa [([)]] non fa parte del linguaggio perché alla posizione 4 si chiude una parentesi tonda e l’ultima parentesi aperta che non ha una corrispondente parentesi chiusa, alla posizione 3, era quadrata. Questo e un caso di interlacciamento.

  1. Dare una grammatica LL(1) per il linguaggio e dare la corrispondente tabella per il parser predittivo
  2. Definire, basandosi sulla grammatica data, una definizione guidata dalla sintassi che calcoli, per il simbolo iniziale, due attributi $t$ e $q$ di tipo $int$. Data una certa stringa $s$, l’attributo $t$ della radice dell’albero di derivazione deve valere quanto il numero di parentesi tonde bilanciate in $s$ e l’attributo $q$ della radice dell’albero di derivazione deve valere quanto il numero di parentesi bilanciate in $s$ Esempi: