Automi

Question 1

Come si definisce un automa a stati finiti?

Answer 1

Un automa a stati finiti si definisce come una quintupla (Q, Σ (sigma), δ (delta), q0, F), dove

• Q è un insieme finito chiamato insieme degli stati
• Σ è un insieme finito chiamato alfabeto,
• δ : Q x Σ -> Q è la funzione di transizione,
• q0 ∈ Q è lo stato iniziale,
• F ∈ Q è l’insieme di stati accettanti

Question 2

Quando un linguaggio è chiamato regolare?

Answer 2

Un linguaggio è definito regolare se esiste un automa finito che lo riconosce.

Question 3

Come sono definite le operazioni regolari?

Answer 3

Siano A e B due linguaggi.
Le operazioni regolari sono definite come:
- Unione: A⋃B = {x| x ∈ A o x ∈ B}
- Concatenazione: AoB = {xy| x∈A e y∈B}
- Star: A* = {x1, x2, …, xk| k>=0 e ogni xi ∈ A}

Question 4

Dimostra che la classe dei linguaggi regolari è chiusa rispetto all’operazione dell’unione.

Answer 4

Bisogna dimostrare che se A1 e A2 sono linguaggi regolari, lo è anche A1⋃A2.

Supponiamo che:
- M1 riconosca A1 con M1 = (Q1, Σ, δ1, q1, F1) e
- M2 riconosca A2 con M2 = (Q2, Σ, δ2, q2, F2)

Costruiamo M = (Q, Σ, δ, q0, F)

• Q = {(r1, r2)| r1}