NON GARANTISCO LA CORRETTEZZA DEGLI ESERCIZI
Il nome di ogni esercizio è dato dal numero della slide più il numero della pagina in cui si trova e da una lettera se presenti più esercizi nella stessa pagina.
- Tutorato 01
- Tutorato 02
- Tutorato 03
- 01-intro-dfa
- 02-03-nfa
- 04-epsilon
- 05-regexp
- 06-esercizi-er
- 07-dfa2re
- 08-pumpinglemma
- 09-esercizi-pl
- 10-chiusure
- 11-fm-esercizi
- Credits
Link repository ALIENK9
DFA che accetta tutte le stringhe che iniziano o finiscono con 01.
@import "immagini/tut01A.png"- Raccolta esercizi
DFA che accetta tutte le stringhe che contengono almeno 2 zeri lunghe 5 caratteri.
@import "immagini/tut01B.png"- Raccolta esercizi
Trasformare da NFA a DFA.
@import "immagini/tut01CConsegna.png"- Raccolta esercizi
@import "immagini/tut01C.png"- Raccolta esercizi
Vedi esercizio 25 slide 02. LINK
Trasformare da
@import "immagini/tut01EConsegna.png"- Raccolta esercizi
Chiusura = insieme di tutti gli stati in cui si può arrivare seguendo le
ENCLOSE (
| a | b | c | |
|---|---|---|---|
| *${q_1,q_2}$ | |||
| *${q_2}$ | |||
@import "immagini/tut01E.png"- Raccolta esercizi
DFA che accetta multipli di 3 in binario.
@import "immagini/tut01F.png"- Raccolta esercizi
In questo caso bisogna prendere il binario e dividerlo per 3 e poi osservare i resti. Gli stati rappresentano:
-
$q_0$ tutti i binari con resto 0 -
$q_1$ tutti i binari con resto 1 -
$q_2$ tutti i binari con resto 2
Ci interessa resto 0 per trovare i multipli di 3 quindi
Espressioni regolari con:
-
2 oppure 3
bcon$\Sigma$ ={a,b} a*ba*ba*(ba*+$\varepsilon$) -
numero di zeri multiplo di 5 con
$\Sigma$ ={0,1} (1*01*01*01*01*01*)*1* -
lunghezza stringa multiplo di 3 con
$\Sigma$ ={a,b,c}* ((a+b+c)(a+b+c)(a+b+c))*
Link repository ALIENK9
L = {0$^p$: con p potenza di 2} è regolare?
Link repository ALIENK9
Automa che accetta il linguaggio delle stringhe con 01 come sottostringa.
@import "immagini/0122.png"- Raccolta esercizi
Insieme di tutte e sole le stringhe con un numero pari di 0 e un numero pari di 1.
@import "immagini/0123A.png"- Raccolta esercizi
Insieme di tutte le stringhe che finiscono con 00.
@import "immagini/0123B.png"- Raccolta esercizi
Insieme di tutte le stringhe che contengono esattamente tre zeri (anche non consecutivi).
@import "immagini/0123C.png"- Raccolta esercizi
Insieme delle stringhe che cominciano o finiscono (o entrambe le cose) con 01.
@import "immagini/0123D.png"- Raccolta esercizi
Modellare il comportamento di un distributore di bibite con un DFA. Il modello deve rispettare le seguenti specifiche:
- Costo della bibita: 40 centesimi
- Monete utilizzabili: 10 centesimi, 20 centesimi
- Appena le monete inserite raggiungono o superano il costo della bibita, il distributore emette una lattina
- Il distributore dà il resto (se serve) subito dopo aver emesso la lattina
@import "immagini/0124.png"- Raccolta esercizi
Insieme di tutte le stringhe che finiscono con 01.
@import "immagini/0205E.png"- Raccolta esercizi
Riconosce le parole che terminano con 01 “scommettendo” se sta leggendo gli ultimi due simboli oppure no
@import "immagini/0207.png"- Raccolta esercizi
L’insieme delle parole sull’alfabeto {0, 1, . . . , 9} tali che la cifra finale sia comparsa in precedenza.
@import "immagini/0212A.png"- Raccolta esercizi
L’insieme delle parole sull’alfabeto {0, 1, . . . , 9} tali che la cifra finale non sia comparsa in precedenza.
@import "immagini/0212B.png"- Raccolta esercizi (Non vale per stringhe con solo 1 cifra ripetuta più di una volta)
L’insieme delle parole di 0 e 1 tali che esistono due 0 separati da un numero di posizioni multiplo di 4 (0 è un multiplo di 4).
@import "immagini/0212C.png"- Raccolta esercizi
Consideriamo l’alfabeto Σ = {a, b, c, d} e costruiamo un automa non deterministico che riconosce il linguaggio di tutte le parole tali che uno dei simboli dell’alfabeto non compare mai:
- tutte le parole che non contengono a
- +tutte le parole che non contengono b
- +tutte le parole che non contengono c
- +tutte le parole che non contengono d
@import "immagini/0213.png"- Raccolta esercizi
Determinare il DFA equivalente all’NFA con la seguente tabella di transizione:
| 0 | 1 | |
|---|---|---|
| {$q_0$} | {$q_0$,$q_1$} | |
| {$q_1$} | {$q_0$,$q_2$} | |
| *$q_2$ | {$q_1$,$q_2$} | {$q_0$,$q_1$,$q_2$} |
@import "immagini/0223.png"- Raccolta esercizi
Qual è il linguaggio accettato dall’automa?
Tutte le stringhe che appartengono all'alfabeto (0,1) e che contengono almeno due 1.
Trasformare il seguente NFA in DFA.
@import "immagini/0224Consegna.png"- Raccolta esercizi
@import "immagini/0224.png"- Raccolta esercizi
Determinare il linguaggio riconosciuto dall’automa. Costruire un DFA equivalente.
@import "immagini/0225Consegna.png"- Raccolta esercizi
Tutte le stringhe che terminano per 001 o 110.
@import "immagini/0225.png"- Raccolta esercizi
Convertire il seguente NFA in DFA:
| 0 | 1 | |
|---|---|---|
| $\rightarrow$A | {A,C} | {B} |
| *B | {C} | {B} |
| C | {B} | {D} |
| D | {$\emptyset$} | {$\emptyset$} |
@import "immagini/0402.png"- Raccolta esercizi
Costruiamo un NFA che accetta numeri decimali:
- Un segno
+o−(opzionale) - Una stringa di cifre decimali {0, . . . , 9}
- Un punto decimale
. - Un’altra stringa di cifre decimali
- Una delle stringhe e può essere vuota, ma non entrambe
@import "immagini/0404.png"- Raccolta esercizi
-
Costruiamo un ε-NFA che riconosce le parole costituite da:
- zero o più a
- seguite da zero o più b
- seguite da zero o più c
@import "immagini/0418.png"- Raccolta esercizi
-
Calcolare ECLOSE di ogni stato dell’automa
- ECLOSE(q0) = {q0, q1, q2}
- ECLOSE(q1) = {q1, q2}
- ECLOSE(q2) = {q2}
-
Convertire l’ε-NFA in DFA
Vedi esercizio E tutorato 01 Link
Scriviamo l’espressione regolare per L = {w ∈ {0, 1}$^*$ : 0 e 1 alternati in w}.
(01)$^$ + (10)$^$ + 1(01)$^$ + 0(10)$^$
Oppure
(
Costruire una ER sull’alfabeto {a, b, c} tale che tutte le stringhe w che contengono un numero pari di a;
(b+c)$^$ (a(b+c)$^
Costruire una ER sull’alfabeto {a, b, c} tale che tutte le stringhe w che contengono 4k + 1 occorrenze di b, per ogni k ≥ 0.
(a+c)$^$b(b(a+c)$^
Costruire una ER sull’alfabeto {a, b, c} tale che tutte le stringhe la cui lunghezza è un multiplo di 3.
((a+b+c)(a+b+c)(a+b+c))$^*$
Costruire una ER sull’alfabeto {0, 1} tale che tutte le stringhe w che contengono la sottostringa 101.
(0+1)$^$101(0+1)$^$
Costruire una ER sull’alfabeto {0, 1} tale che tutte le stringhe w che non contengono la sottostringa 101.
0$^$(1+000$^
Costruire una ER sull’alfabeto {0, 1} per il linguaggio di tutti i numeri binari multipli di 3.
0$^$((1(01$^
Trasformare (0 + 1)$^*$1(0 + 1) in
@import "immagini/0520.png"- Raccolta esercizi
Trasformiamo (0+1)$^*$1(0+1) in
@import "immagini/0607A.png"- Raccolta esercizi
Scrivere un’espressione regolare per rappresentare il linguaggio sull’alfabeto {a, b, c} che contiene tutte le stringhe che:
- iniziano con a e sono composte solo di a oppure b
- la stringa c
La prima condizione si potrebbe interpretare in 2 modi diversi.
- a(a+b)$^*$+c
- a(a*+b*)+c
Trasformare l’espressione regolare dell’esercizio 2 in
Primo caso:
@import "immagini/0607C1.png"- Raccolta esercizi
Secondo caso:
@import "immagini/0607C2.png"- Raccolta esercizi
Scrivere una espressione regolare per tutte stringhe binarie che cominciano e finiscono per 1.
1(0+1)$^*$1+1
@import "immagini/0608A.png"- Raccolta esercizi
Scrivere una espressione regolare per le stringhe binarie che contengono almeno tre 1 consecutivi.
(0+1)$^$ 111 (0+1)$^$
Scrivere una espressione regolare per le stringhe binarie che contengono almeno tre 1 (anche non consecutivi).
(0+1)$^$ 1 (0+1)$^$ 1 (0+1)$^$ 1 (0+1)$^$
oppure
(0+1)$^$ 1 0$^$ 1 0$^$ 1 (0+1)$^$
Scrivere una espressione regolare per stringhe di testo che descriva le date in formato GG/MM/AAAA.
0(1+...+9)+(1+2)(0+..+9)+3(0+1)/0(1+...+9)+1(0+...+2)/(0+...+9)$^4$
Ovviamente non controlla gli anni bisestili e nemmeno che ci siano 30 o 31 giorni in un determinato mese.
Costruiamo l’espressione regolare equivalente al seguente NFA:
@import "immagini/0707AConsegna.png"- Raccolta esercizi
Eliminando gli stati
Sommando le 2 espressioni precedenti si ottiene la ER cercata: ((0+1)$^$1(0+1)(0+1))+(0+1($^$1(0+1))
Costruiamo l’espressione regolare equivalente al seguente NFA:
@import "immagini/0707BConsegna.png"- Raccolta esercizi
@import "immagini/0707B.png"- Raccolta esercizi
Costruiamo l’espressione regolare equivalente al seguente NFA:
@import "immagini/0708Consegna.png"- Raccolta esercizi
(1+0(10$^$1+0)(1(10$^
Sia
No,
-
supponiamo per assurdo che lo sia
-
sia
$n$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = a^nb^{n+1}$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ n$ :$w = \underbrace{aa...}{x} \underbrace{...aa}{y} \underbrace{abbbbb}_{z}$
-
per il Pumping Lemma, anche
$xy^2z$ ∈$L_{ab}$ , ma contiene più a che b ⇒ assurdo.
Il linguaggio
No,
-
supponiamo per assurdo che lo sia
-
sia
$n$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = a^nbba^n$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ n$ :$w = \underbrace{aa...}{x} \underbrace{...aa}{y} \underbrace{abbaaa..aa}_{z}$
-
per il Pumping Lemma, anche
$xy^0z = xz ∈ L_{rev}$ , ma non la posso spezzare in$ww^R$ ⇒ assurdo.
Il linguaggio
Sì,
- è rappresentato dall’espressione regolare a(aa)$^$b$^$ + a$^$(bb)$^$
- e riconosciuto dall'automa
@import "immagini/0813.png"- Raccolta esercizi
Sia
No,
-
supponiamo per assurdo che lo sia
-
sia
$h$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = a^hb^h$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ h$ :$w = \underbrace{aa...aa}{x} \underbrace{a...a}{y} \underbrace{a...abb...bbb}_{z}$
-
poiché
$\mid xy \mid ≤ h$ , le stringhe x e y sono fatte di solea -
per il Pumping Lemma, anche
$xy^2z$ ∈$L_{ab}$ , ma contiene più a che b ⇒ assurdo.
Vedi esercizio 12 slide 08. LINK
Vedi esercizio 13 slide 08. LINK
Il linguaggio
No,
-
supponiamo per assurdo che lo sia
-
sia
$h$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = 1^p$ con$p$ primo e$p > h+2$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ h$ :$w = \underbrace{11...11}{x} \underbrace{11...11}{y} \underbrace{11...11}_{z}$
-
sia
$\mid y \mid = m$ allora$\mid xy \mid = p - m$ -
per il Pumping Lemma, anche
$v=xy^{p-m}z$ ∈$L_p$ -
allora
$\mid v \mid = m(p-m)+p-m=(p-m)(m+1)$ sì può scomporre in due fattori -
poiché
$y \ne \varepsilon$ , allora$|y| = m > 0$ e$m + 1 > 1$ -
anche $ p - m > 1$ perché abbiamo scelto
$p > h + 2$ e$m ≤ h$ perché$|xy| ≤ h$ -
i due fattori sono entrambi maggiori di 1 e quindi
$\mid v \mid$ non è un numero primo -
$v \not \in L_p$ , assurdo.
Il linguaggio
Sì,
- è rappresentato dall’espressione regolare (111)$^*$11
- e riconosciuto dall'automa
@import "immagini/0909A.png"- Raccolta esercizi
Il linguaggio
No,
-
supponiamo per assurdo che lo sia
-
sia
$h$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = 0^n1^m0^n$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ h$ :$w = \underbrace{00...00}{x} \underbrace{0...0}{y} \underbrace{00..0011..1100..00}_{z}$
-
poiché
$\mid xy \mid ≤ h$ , le stringhe x e y sono fatte di soli0 -
per il Pumping Lemma, anche
$xy^2z$ ∈$L_{mn}$ , ma il numero di0a sinistra e destra degli1non è uguale ⇒ assurdo.
Il linguaggio
No,
-
supponiamo per assurdo che lo sia
-
sia
$h$ la lunghezza data dal Pumping Lemma -
consideriamo la parola
$w = a^{2n}b^n$ -
prendiamo un qualsiasi split
$w = xyz$ tale che$y \ne \varepsilon$ e$\mid xy \mid ≤ h$ :$w = \underbrace{aa...aa}{x} \underbrace{a...a}{y} \underbrace{a...abb...bbb}_{z}$
-
poiché
$\mid xy \mid ≤ h$ , le stringhe x e y sono fatte di solea -
per il Pumping Lemma, anche
$xy^2z$ ∈$L_{2a}$ , ma il numero diaè più del doppio del numero delleb⇒ assurdo.
//TODO
Costruire l’automa che riconosce l’intersezione dei linguaggi dei seguenti due automi:
@import "immagini/1112ConsegnaA.png"- Raccolta esercizi @import "immagini/1112ConsegnaB.png"- Raccolta esercizi
Soluzione senza stati finali (
@import "immagini/1112.png"- Raccolta esercizi
Costruire un DFA sull’alfabeto {0, 1} che rappresenti tutte le stringhe w che contengono la sottostringa 101.
@import "immagini/1113A.png"- Raccolta esercizi
Costruire un DFA sull’alfabeto {0, 1} che rappresenti tutte le stringhe w che non contengono la sottostringa 101.
@import "immagini/1113B.png"- Raccolta esercizi
Sia L un linguaggio sull’alfabeto Σ e a ∈ Σ. Definiamo il quoziente di L e a come il linguaggio: L/a = {w ∈ Σ$^*$ : wa ∈ L} Dimostrare che se L è regolare allora anche L/a è regolare.
//todo
Sia L un linguaggio regolare. Dimostrare che anche i seguenti linguaggi sono regolari:
- min(L) = {w : w ∈ L ma nessun prefisso proprio di w è in L}
- max(L) = {w : w ∈ L e per nessuna stringa x
$\ne$ ε, wx ∈ L}
Min sono le parole più corte che appartengono ad L Max sono le parole più lunghe che appartengono ad L Prefesso proprio di w: segmento iniziale di w w=a$_1$......a$_n$ prefisso proprio di w sono tutte le parole a$_1$...a$_k$ con k < n
//todo
- JFLAP
- MPE
- Link Repository per contribuire o segnalare errori