Esercizi svolti: Intersezione tra automi

Si dovrebbe già sapere che l’automa caratterizza un linguaggio regolare. E sappiamo che la classe dei linguaggi regolari è chiusa rispetto all’intersezione (al contrario della classe dei linguaggi liberi), ciò significa che l’intersezione tra due linguaggi regolari genera un altro linguaggio regolare (quindi caratterizzabile da un automa). Ora la domanda è: Dati due linguaggi regolari L1 e L2 caratterizzati dagli … Continua a leggere

Dimostrare che un linguaggio non è libero con il Pumping Lemma linguaggi liberi

Questo è un esercizio svolto per determinare se un linguaggio è libero usando il pumping lemma linguaggi liberi. Quindi bisogna dimostrare che un certo linguaggio L non è libero. Sia un linguaggio, dimostrare che non è libero. Devo usare il Pumping Lemma linguaggi liberi. Quindi tale che Valgono quelle condizioni (1), (2) e (3) Come per il pumping lemma linguaggi … Continua a leggere

Esercizi svolti: Dimostrazione che un linguaggio è libero, teorema di chiusura e pumping lemma

Sia dato il linguaggio dimostrare che è libero e che non è regolare. Si userà: teorema di chiusura e pumping lemma dei linguaggi regolari (tipo 3). Posso dividere L in due linguaggi più semplici, in modo che L = L1 U L2 Per il teorema della chiusura dei linguaggi liberi da contesto rispetto all’operazione unione, se L1 e L2 sono … Continua a leggere

Esercizi svolti: Automa numeri romani DFA

L’esercizio consiste nel generare l’automa a stati finiti deterministico (DFA) dei numeri romani. Innanzitutto come è ovvio, se vogliamo insegnare qualcosa ad una macchina (o anche ad una persona) allora noi dobbiamo essere i primi a conoscerla bene. Quindi chiariamo prima come funziona la notazione dei numeri romani. Si basa su queste regole: I=1, V=5, X=10, L=50, C=100, D=500, M=1000 … Continua a leggere

Esercizi svolti: Pumping Lemma determinare il tipo di un linguaggio

Questo è un esercizio svolto per determinare il tipo di un linguaggio usando eventualmente il pumping lemma. Dato un linguaggio, bisogna determinarne il tipo usando strumenti formali (tra cui il pumping lemma). Il linguaggio proposto è abbastanza semplice, per una sfida più difficile (molto di più) leggere questo articolo. Sia dato il linguaggio determinarne il tipo. Uso il Pumping Lemma … Continua a leggere

Esercizi svolti: Probabilità di fare 6 al superenalotto

Abbiamo un sacchetto in cui sono contenute 90 palline numerate da 1 a 90. Supponiamo di estrarre 6 palline senza reimbossulamento, qual’è la probabilità di indovinare i 6 numeri estratti? Dobbiamo calcolare la probabilita’ dell’estrazione di 6 numeri su 90 possibili, quindi lo spazio di probabilità è la disposizione semplice (senza ripetizioni) di 6 numeri su 90. Cioè in un … Continua a leggere

Esercizi svolti: Traduzione da automa ad espressione regolare

L’esercizio consiste nella traduzione da automa a espressione regolare (automa DFA -> RegExp). L’automa deve essere deterministico (DFA = Deterministic Finite Automata). RegExp = Regular Expression. Questa immagine può essere vista come una mappa stradale dal punto A al punto B. L’obiettivo è descrivere tutti i possibili percorsi tramite una espressione regolare. L’algoritmo da seguire consiste nell’eliminazione progressiva degli stati … Continua a leggere