1. Sia DFA A l’automa che rappresenta in linguaggio L che accetta tutte le stringhe in Σ 0,1 che terminano in 011.

Automi e Linguaggi Formali Homework 3

Argomenti: [EQUIVALENZA, TRASFORMAZIONI, MINIMIZZAZIONE]

1. Sia DFA A l’automa che rappresenta in linguaggio L che accetta tutte le stringhe in Σ ^0,1 che terminano in 011.

0 1

→ q 0 q 1 q 2

q ₁ q ₁ q ₃ q ₂ q ₁ q ₂ q ₃ q ₁ q ₄

?q ₄ q ₁ q ₂

q

start q

q

q

q

0 1

1 0

0 0

1 1

0

1

. Applicare l’algoritmo di riempimento della tabella per identificare le classi di equivalenza in A.

. Disegnare l’automa minimo.

2. Sia DFA A l’automa rappresentato dal seguente diagramma delle tran- sizioni:

q

start

q

q

q

q

q

q

q

q

q

a

b b

b

b b

a

a b a

a

b

a a a a

b

a,b

b

. Applicare l’algoritmo di riempimento della tabella per identificare le classi di equivalenza in A.

. Disegnare l’automa minimo.

3. Sia L il linguaggio definito dalla concatenazione L ₁ L ₂ dei seguenti lin- guaggi sull’alfabeto Σ ^a,b .

- L1 = {w||w| ≤ 1}

- L2 = {w|ogniposizionidispariinwe ⁰ occupatadaunsimbolob}

. Costruire l’NFA corrispondente e minimizzarlo

4. Sia A il DFA descritto dalla seguente tabella di transizione:

0 1

→

? p s p

?q p t

?s t r r r q t r q

. Applicare l’algoritmo di riempimento della tabella per identificare le classi di equivalenza in A.

. Disegnare l’automa minimo.

5. Definire una CFG per i seguenti linguaggi . L = {w ∈ {0, 1} ^∗ tali che |w| e’ dispari

. L = {w ∈ {0, 1} ^∗ tali che |w| e’ dispari e l’elemento mediano e’ 0}

. L = {w ∈ {0, 1} ^∗ tali che w contiene almeno tre 1}

. L = ∅