API 2021 08 25

Page 1

Algoritmi e Principi dell’Informatica T ema d’esame del 25 Agosto 2021 Esercizio 1 (8 punti, si svolgano solo i punti a e c in caso di riduzione del 30%) Si definisca riconoscitore ad automi gemelli (RAG) un meccanismo di calcolo ottenuto facendo ope- rare due automi sullo stesso nastro di ingresso. Gli automi operano indipendentemente sul nastro di ingresso, ognuno di essi accede al nastro attraverso una propria testina. La parola presente sul nastro di ingresso si considera riconosciuta se e solo se i due automi la riconoscono (non necessa- riamente nello stesso numero di mosse). Si consideri il caso dei RAG costruiti come segue e si dica se il loro potere riconoscitore ` e maggiore, minore o uguale a quello delle loro componenti: a) RAG costituito da un automa a stati finiti deterministico e uno non deterministico; b) RAG costituito da un automa a stati finiti deterministico ed un automa a pila deterministico; c) RAG costituito da due automi a pila non deterministici. Soluzione DettiA1 eA2 gli automi che compongono un dato riconoscitore ad automi gemelliA, si osserva che il riconoscitore ad automi gemelli riconosce il linguaggio L(A) = L(A1)∩ L(A2). `E infatti sufficiente osservare che i due automi che lo compongono operano senza influenzarsi e la condizione di accettazione richiede che entrambi accettino la parola sul nastro d’ingresso. Si ha quindi che a) Il riconoscitore ad automi gemelli ha la stessa potenza riconoscitiva delle sue componenti: i linguaggi regolari sono chiusi per intersezione b) Il riconoscitore ad automi gemelli ha la stessa potenza riconoscitiva di un automa a pila deter- ministico. `E possibile derivare questo fatto sia dal fatto che i linguaggi liberi dal contesto sono chiusi rispetto all’intersezione con i linguaggi regolari. Alternativamente, `…