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

Teoria dei limiti per lo studio della complessità computazionale. O-grande

In questo articolo cerco di porre la base della teoria dei limiti per lo studio della complessità computazionale. Ci tengo subito a chiarire che non affronto calcoli dei limiti, il mio scopo è la complessità computazionale, non i limiti. Sostanzialmente sono concetti che si dovrebbero già teoricamente conoscere dalla matematica scolastica. Probabilmente alcuni esperti potrebbero un po’ “storcere il naso” … 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