API 2020 06 26

Pagina 1

Algoritmi e Principi dell’Informatica Soluzioni al T ema d’esame 26 Giugno 2020 1 Informatica teorica Esercizio 1 (prima variante) Si consideri l’alfabeto A ={d, s, t} e il linguaggio L di tutte e sole le stringhe su A che soddisfano i requisiti seguenti: 1. ogni stringa inizia con un prefisso che pu` o essere la stringa vuota, la stringa d o la stringa ds; 2. dopo il prefisso, c’` e la sequenza tds ripetuta un numero arbitrario di volte (anche nessuna volta); 3. infine, la stringa si chiude con la sequenza ts; 4. la sequenza dtd non appare mai all’interno della stringa; 5. la stringa contiene tutti e tre i simboli alfabetici. Esempi di stringhe appartenenti al linguaggio sono: dts, dsts, tdsts, dstdsts, tdstdsts. Esempi di stringhe non appartenenti al linguaggio sono: ddts, dtdsts, ts, d. Scrivere una grammatica a potenza generativa minima che generi L. Soluzione Basta una grammatica regolare. Il vincolo 5 impone che, in caso di prefisso vuoto, la sequenza tds sia ripetuta almeno una volta. Il vincolo 4 significa che, in caso di prefisso d, la sequenza tds sia ripetuta zero volte. L’espressione regolare corrispondente a L ` e la seguente: dts|((tds|ds)(tds)∗ts) Una grammatica regolare ` e come segue: S→ A|B|C A→ tB B→ dD D→ sA|sL C→ dL L→ tM M→ s Un modo equivalente per risolvere l’esercizio ` e di iniziare con una grammatica non regolare che genera il linguaggio: S→ dts|tdsR|dsR R→ tdsR|ts e di trasformarla in una grammatica regolare evitando le sequenze di terminali: 1/6 S→ tS1|dS6 S1→ dS2 S2→ sS3 S3→ tS4|tS7 S4→ dS5 S5→ sS3 S6→ tS3|tS7 S7→ s Esercizio 1 (seconda variante) Testo e soluzione sono come nella prima variante, dopo aver opportunamente sostituito t con f, s con q e d con r. Esercizio 2 (prima variante) Per ciascuno dei seguenti insiemi si stabilisca, fornendo…