Esercitazione III

(1)

OSTRUZIONE

UTOMI A

TATI

INITI PER IL

ICONOSCIMENTO DI

INGUAGGI

EGOLARI

Dato il Linguaggio:

 generare la grammatica

 darne la classificazione

 costruire l’automa a stati finiti per il suo riconoscimento

1. (d^*ab)⁺d⁺(a^*b)^*c 2. (a⁺b⁺)⁺(dca^*|cb⁺(ab)^*) 3. (ab^*(fb)⁺|dc^*a)^*ec^* 4. (a^*b⁺c)⁺((db)^*)⁺ 5. ((a^*b⁺c)⁺(db)^*)⁺

6. (a⁺b⁺c)⁺(db|bg)^*(e⁺d⁺a^*b^*)⁺ 7. (a⁺b^*c⁺)⁺(a⁺(cb)^*c⁺)^*

(2)

OLUZIONI

1. (d^*ab)⁺d⁺(a^*b)^*c S -> Ac

{1,3}

{1,4,5}

{2,5}

{5,6}

{1,3,5,6}

(3)

2. (a⁺b⁺)⁺(dca^*|cb⁺(ab)^*) S -> aS | aA

A -> bA |bS | bB B -> dcC | cD C -> aC | ε D -> bD | bE E -> abE | ε

Tipo 3

Tipo 3

4. (a^*b⁺c)⁺((db)^*)⁺

(4)

S -> aS | A

A -> bA | bcS | bcB B -> dbB | ε

Tipo 3

5. ((a^*b⁺c)⁺(db)^*)⁺ S -> aS | A

A -> bA | bcS | bcB B -> dbB | S | ε Tipo 3

6. (a⁺b⁺c)⁺(db|bg)^*(e⁺d⁺a^*b^*)⁺

(5)

S -> aS | aA

7. (a⁺b^*c⁺)⁺(a⁺(cb)^*c⁺)^* S  aS | aA

{5,7}