linguaggi formali e traduttori - wordpress.com · 2020. 1. 23. · linguaggi formali e traduttori...
TRANSCRIPT
-
Linguaggi Formali e TraduttoriEsercitazioni(2019/2020)
Docente: Luigi Di Caro Email: [email protected]
-
DisclaimerIl contenuto di queste slide non è in alcun modo da intendersi come sostitutivo delmateriale e delle indicazioni fornite dai docenti di riferimento. Inoltre, gli esercizi propostinon coprono l’intero programma del corso.
Lo scopo delle esercitazioni è principalmente quello di risolvere eventuali dubbirisolvendo alcuni specifici esercizi, affrontandoli con maggior tempo a disposizione, passoper passo.
Si ricorda inoltre che agli esami ogni compito verrà corretto dal proprio docente diriferimento, secondo le nozioni e gli strumenti forniti nei rispettivi corsi A/B.
-
Linguaggi Formali e Traduttori esercitazioni
• Linguaggi regolari• Automi a stati finiti• Deterministici / Non deterministici• Espressioni regolari• Minimizzazione automi a stati finiti
PARTE I
-
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
PARTE I
-
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…(ii) Le stringhe possono iniziare sia con a che con b: (a+b)aa…bb…
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…(ii) Le stringhe possono iniziare sia con a che con b: (a+b)aa…bb…
E allora la stringa che inizia con “ab”?
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…(ii) Le stringhe possono iniziare con sequenze arbitrarie di a e b: (a+b)*aa…bb…
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…(ii) Le stringhe riconosciute possono iniziare sia con a che con b: (a+b)*aa…bb…(iii) Le stringhe possono finire con sequenze arbitrarie di a e b: (a+b)*aa…bb(a+b)*
-
PARTE I
Note: (i) Inizio con inserire aa e bb all’interno dell’espressione regolare: …aa…bb…(ii) Le stringhe riconosciute possono iniziare sia con a che con b: (a+b)*aa…bb…(iii) Le stringhe riconosciute possono finire sia con a che con b: (a+b)*aa…bb(a+b)*(iv) Le stringhe riconosciute possono avere sequenze di a e b tra aa e bb:
(a+b)*aa(a+b)*bb(a+b)*
Si consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
(a+b)*aa(a+b)*bb(a+b)*
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
(a+b)*aa(a+b)*bb(a+b)*
?
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
(a+b)*aa(a+b)*bb(a+b)*
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
1 [A,B,C] [A,B,C] [A]
2 [A,B,C] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,B,C] [A,B,C] [A,C,D,E]
5 [A,B,C,E] [A,B,C,E] [A,C,D,E]
6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,B,C] [A,B,C] [A,C,D,E]
5 [A,B,C,E] [A,B,C,E] [A,C,D,E]
6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,B,C] [A,B,C] [A,C,D,E]
5 [A,B,C,E] [A,B,C,E] [A,C,D,E]
6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
->1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,C,D] [A,B,C] [A,C,D,F]
*5 [A,C,D,F] [A,B,C,F] [A,C,D,F]
*6 [A,B,C,F] [A,B,C,F] [A,C,D,F]
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
->1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,C,D] [A,B,C] [A,C,D,E]
*5 [A,C,D,E] [A,B,C,E] [A,C,D,E]
*6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
?
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
->1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,C,D] [A,B,C] [A,C,D,E]
*5 [A,C,D,E] [A,B,C,E] [A,C,D,E]
*6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
?
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
a b
->1 [A] [A,B] [A]
2 [A,B] [A,B,C] [A]
3 [A,B,C] [A,B,C] [A,C,D]
4 [A,C,D] [A,B,C] [A,C,D,E]
*5 [A,C,D,E] [A,B,C,E] [A,C,D,E]
*6 [A,B,C,E] [A,B,C,E] [A,C,D,E]
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23456
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23456
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2345 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2345 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2345 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
234 ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23 ii4 ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23 ii4 ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23 ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
23 ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2 iii3 ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2 iii3 iii ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2 iii3 iii ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
2 iii3 iii ii4 ii ii ii5 i i i i6 i i i i
1 2 3 4 5
Attraverso tabella triangolare(corso B)
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
Attraverso partizionamento (corso A)
Costruiamo le partizioni P0, P1, …, Pk, fino a quando Pk = Pk-1.
P0 ha due sottinsiemi: stati finali e stati non finali.
P0 = {1, 2, 3, 4}, {5, 6}
Pi: per ogni coppia di stati nello stesso insieme Pi-1, si deve verificare se d(qi, a) e d(qj, a) sono stati equivalenti i-1, cioè appartengono allo stesso insieme della partizione Pi-1 e così anche per d(qi, b) e d(qj, b).
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
Attraverso partizionamento(corso A)
Costruiamo le partizioni P0, P1, …, Pk, fino a quando Pk = Pk-1.
P0 = {1, 2, 3, 4}, {5, 6}P1 = {1, 2, 3}, {4}, {5, 6}P2 = {1, 2}, {3}, {4}, {5, 6}P3 = {1}, {2}, {3}, {4}, {5, 6}P4 = {1}, {2}, {3}, {4}, {5, 6} = P3
Ad esempio, nella partizione P2 gli stati 1 e 3 sono in insiemi diversi in quanto d(1, b) = 1 e d(3, b) = 4, e in P1 2 e 4 sono in insiemi diversi.
-
PARTE ISi consideri il linguaggio formato da tutte e sole le stringhe sull’alfabeto {a, b} checontengono almeno un’occorrenza delle sottostringhe aa e bb, nell’ordine.
1. Definire l’espressione regolare;2. Costruire l’automa non deterministico;3. Costruire l’automa deterministico;4. Costruire l’automa deterministico minimo.
Gli unici stati indistinguibili sono gli stati 5 e 6.
Attraverso partizionamento(corso A)
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
??
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
?
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
?
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
2 ii
3 i i
1 2
?1 = p2 = q3 = r
Attraverso tabella triangolare(corso B)
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
L’automa è già minimo, infatti:
2 ii
3 i i
1 2
Cioè non esistono coppie indistinguibili.
Attraverso tabella triangolare (corso B)
-
Dato il seguente epsilon-NFA:
1. Costruire l’automa deterministico;2. Disegnare l’automa deterministico;3. Costruire l’automa deterministico minimo.
PARTE I
Attraverso partizionamento (corso A)
P0 = {[p], [p, q]}, {[p, q, r]}
P1 = {[p]}, {[p, q]}, {[p, q, r]}
Gli stati sono tutti distinguibili L’automa è già minimo
-
Dato il seguente epsilon-NFA:
1. Qual’è l’epsilon-chiusura degli stati?
PARTE I
-
Dato il seguente epsilon-NFA:
1. Qual’è l’epsilon-chiusura degli stati?
PARTE I
eps-close(p) = {p}eps-close(q) = {q, p}eps-close(r) = {r, p, q}
-
1. Costruire un DFA che riconosca il linguaggio { (a+b)nCm I n≥0, m>0 }.2. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0, m>0 }.3. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0 pari, m>0 dispari}.
PARTE I
-
1. Costruire un DFA che riconosca il linguaggio { (a+b)nCm I n≥0, m>0 }.2. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0, m>0 }.3. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0 pari, m>0 dispari}.
PARTE I
?
?
?
-
1. Costruire un DFA che riconosca il linguaggio { (a+b)nCm I n≥0, m>0 }.2. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0, m>0 }.3. Costruire un DFA che riconosca il linguaggio { (ab)nCm I n≥0 pari, m>0 dispari}.
PARTE I
3
2
1
C