ESERCITAZIONE I Linguaggi Regolari

INTRODUZIONE

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

2

Il percorso di

trasformazioni in

grigio sarà il primo

ad essere analizzato,

mentre il rosso verrà

trattato in seguito.

Il percorso in

azzurro verrà

inserito all’interno

degli altri esercizi

Il percorso arancione

sarà oggetto della

conclusione

dell’esercitazione

TIPI DI TRASFORMAZIONI

3

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

ASFD

ASFND

ER

GR

NOTE & FAQS

4

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Useremo per gli ASF una nomenclatura per gli stati molto semplice: lo stato iniziale è q0, il secondo stato q1 e così via.

Potete usare la nomenclatura che preferite, come START per lo stato iniziale o A per uno stato che legge la pima ‘a’ di una stringa e simili, purché identificativa e coerente.

Stesso discorso per i simboli non terminali delle grammatiche, che verranno qui identificati con S se assioma e con N ed un apice in caso contrario.

Non prenderemo oggi in esame né automi con ε-transizioni né grammatiche con ε-produzioni, rimandando al libro di testo ulteriori dettagli

ESERCIZI PARTE I

o dall’espr regolare all’ASF

o dall’ASF alla grammatica di tipo 3

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

5

ESERCIZIO 1 (ER – ASF)

Scrivere l’ASF che riconosce il linguaggio descritto

dall’espressione regolare (a+b)*bba.

6

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

q3 q0 q1 q2

b b a

a b

a b

a

E’ l’automa precedente DETERMINISTICO?

Si’. Perché?

S → a S | b N1

N1 → a S | b N2

N2 → a N3 | a | b N2

N3 → a S | b N1

ESERCIZIO 1 (ASF – GR)

Scrivere la grammatica di tipo 3 corrispondente

all’ASF appena costruito.

7

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

b b a

a b

a b

a

Una grammatica, poiché descrive un linguaggio

secondo un approccio generativo, è sovrapponibile

all’automa che riconosce il linguaggio.

ESERCIZIO 2 (ER – ASF)

Scrivere l’ASF che riconosce il linguaggio descritto

dall’espressione regolare (a*ba*b)+.

8

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

E’ l’automa precedente DETERMINISTICO?

Si’. Perché?

q3 q0 q1

b b

a a

a

b

Scrivere la grammatica di tipo 3 corrispondente

all’ASF appena costruito.

S → a S | b N1

N1 → a N1 | b | b N2

N2 → a S | b N1

ESERCIZIO 2 (ASF – GR)

9

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Si noti come nella parte destra di ogni produzione

compaiono produzioni terminali in corrispondenza

di transizioni verso uno stato finale.

b b

a a

a

b

ESERCIZI PARTE II

o dall’espr regolare alla grammatica di tipo 3

o dalla grammatica di tipo 3 all’ASF

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

10

Scrivere la grammatica di tipo 3 che genera il

linguaggio descritto dall’espressione regolare

(a+b+b+a).

S → a NA | b NB

NA → a NA | b

NB → b NB | a

ESERCIZIO 3 (ER – GR)

11

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Si noti che NA che genera le produzioni relative al

solo a+b ed NB quelle relative a b+a.

ESERCIZIO 3 (GR – ASF)

Scrivere l’ASF che riconosce il linguaggio generato

dalla grammatica appena scritta.

12

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

q3 q0

q1

a b

a

q2

b

a b

Il problema è molto simile ad ASF GR.

E’ l’automa DETERMINISTICO? No. Perché?

Scrivere la grammatica di tipo 3 che genera il

linguaggio descritto dall’espressione regolare

a(a+b)*b.

S → a N1

N1 → a N1 | b N1 | b

ESERCIZIO 4 (ER – GR)

13

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

ESERCIZIO 4 (GR – ASF)

Scrivere l’ASF che riconosce il linguaggio generato

dalla grammatica appena scritta.

14

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

q2 q0 q1

a b

a,b

E’ l’automa precedente DETERMINISTICO?

No. Perché?

TRASFORMAZIONE DA ASFD A ASFND

Sia A l’automa ND, A è una quintupla <Σ, K, q0, δ, F>

Sia A’ l’ASFD corrispondente <Σ’, K’, q0’, δ’, F’>

L’alfabeto Σ’ di A’ coincide con Σ

L’insieme K’ degli stati di A’ è in corrispondenza biunivoca con l’insieme delle parti di K

Lo stato iniziale q0’ di A’ corrisponde al singleton {q0}

L’insieme degli stati finali F’ di A’ corrisponde all’insieme dei sottoinsiemi di K con intersezione non vuota con F

La funzione di transizione δ’ di A’ mappa ogni coppia (x, c) nello stato y che corrisponde alla unione di tutti gli insiemi di stati dove δ, alla lettura di c, mappa rispettivamente ogni stato di A che appartiene ad x

15

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

ESERCIZIO 4 (ASFND – ASFD)

Trasformare l’ASFND appena scritto in un ASFD.

16

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Uno: Nuova funzione di transizione con 2|K| stati

a b

a,b

δ([], a) = [] δ([], b) = []

δ([q0], a) = [q1] δ([q0], b) = []

δ([q1], a) = [q1] δ([q1], b) = [q1,q2]

δ([q2], a) = [] δ([q2], b) = []

δ([q0,q1], a) = [q1] δ([q0,q1], b) = [q1,q2]

δ([q0,q2], a) = [q1] δ([q0,q2], b) = []

δ([q1,q2], a) = [q1] δ([q1,q2], b) = [q1,q2]

δ([q0,q1,q2], a) = [q1] δ([q0,q1,q2], b) = [q1,q2]

ESERCIZIO 4 (ASFND – ASFD)

Trasformare l’ASFND appena scritto in un ASFD.

17

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Due: Individuare gli stati raggiungibili da q0

δ([], a) = [] δ([], b) = []

δ([q0], a) = [q1] δ([q0], b) = []

δ([q1], a) = [q1] δ([q1], b) = [q1,q2]

δ([q2], a) = [] δ([q2], b) = []

δ([q0,q1], a) = [q1] δ([q0,q1], b) = [q1,q2]

δ([q0,q2], a) = [q1] δ([q0,q2], b) = []

δ([q1,q2], a) = [q1] δ([q1,q2], b) = [q1,q2]

δ([q0,q1,q2], a) = [q1] δ([q0,q1,q2], b) = [q1,q2]

a b

a,b

ESERCIZIO 4 (ASFND – ASFD)

Trasformare l’ASFND appena scritto in un ASFD.

18

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Tre: Individuare gli stati finali, i.e. contenenti q2

δ([], a) = [] δ([], b) = []

δ([q0], a) = [q1] δ([q0], b) = []

δ([q1], a) = [q1] δ([q1], b) = [q1,q2]

δ([q2], a) = [] δ([q2], b) = []

δ([q0,q1], a) = [q1] δ([q0,q1], b) = [q1,q2]

δ([q0,q2], a) = [q1] δ([q0,q2], b) = []

δ([q1,q2], a) = [q1] δ([q1,q2], b) = [q1,q2]

δ([q0,q1,q2], a) = [q1] δ([q0,q1,q2], b) = [q1,q2]

a b

a,b

ESERCIZIO 4 (ASFND – ASFD)

Trasformare l’ASFND appena scritto in un in un

ASF deterministico.

19

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Si noti l’aumento del numero degli stati,

potenzialmente esponenziale

q1,q2 q0 q1

a b

a

- b

b

a

ESERCIZI PARTE III

o dalla grammatica di tipo 3 all’espr regolare

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

20

TRASFORMAZIONE DA GR A ER

Scrivere un sistema derivato dalla grammatica di tipo 3:

Ogni produzione un’equazione

Ogni simbolo non terminale una variabile

Ogni simbolo terminale una costante

‘|’ diventa ‘+’

Eliminare la ricorsione se necessario:

S = aS + X S = a* X

S = aS + a S = a* a = a+

Applicare il principio di sostituzione delle variabili finché non si ottiene la sola equazione relativa all’assioma.

Il membro destro dell’equazione è l’espressione regolare che descrive il linguaggio generato dalla grammatica di tipo 3.

21

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

ESERCIZIO 5 (GR – ER)

Scrivere l’espressione regolare che descrive il

linguaggio generato dalla grammatica di tipo 3

22

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Uno: Scrivere il sistema corrispondente alla GR

S → a S | b N1

N1 → a N1 | b N2 | b

N2 → a N2 | a

S = a S + b N1

N1 = a N1 + b N2 + b

N2 = a N2 + a

ESERCIZIO 5 (GR – ER)

Scrivere l’espressione regolare che descrive il

linguaggio generato dalla grammatica di tipo 3

23

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Due: Eliminare la ricorsione

S = a* b N1

N1 = a* (b N2 + b)

N2 = a+

S = a S + b N1

N1 = a N1 + b N2 + b

N2 = a N2 + a

ESERCIZIO 5 (GR – ER)

Scrivere l’espressione regolare che descrive il

linguaggio generato dalla grammatica di tipo 3

24

Fon

da

men

ti di In

form

atica

II - D. F

irma

ni

Tre: Sostituire le variabili e semplificare

S = a* (b N1)

N1 = a* (b N2 + b)

N2 = a+

S = a* b N1

N1 = a* (ba+ + b)

1

S = a* b N1

N1 = a* ba*

2

S = a* ba* ba* 3