Linguaggi di programmazione: es. 8 espressione regolare

Esercizio espressione regolare

Dato il linguaggio fare una DFA M, scrivere G regolare e ricavare l’espressione regolare:

L = {01ⁿ | n > 0, n ≠ 5}

Costruiamo l’automa DFA:

M = (Σ, Q, δ, q₀, F)

Scriviamo la grammatica regolare:

G = (X,V,S,P)
X = {0,1}
V = {S,A,B,C,D,E,F,G}

P = {
S -> 0A
A -> 1B
B -> 1C | λ
C -> 1D | λ
D -> 1E | λ
E -> 1F | λ
F -> 1G
G -> 1G | λ
}

Troviamo l’espressione regolare di questo automa:

Quindi:

Usando l’algoritmo (R*+SU*T)*SU* avremo la seguente espressione:

01+011+0111+01111+01111111*