Linguaggi di programmazione: es. 7 espressione regolare

Esercizio espressione regolare

Data la grammatica ricavare un automa DFA e un’espressione regolare tale che R = L(G):

S -> bA | aS | b
A -> aB | cS | a
B -> bA | cB | c

Costruiamo l’automa DFA:

Troviamo l’espressione regolare di questo automa:

Quindi:

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

(a+bc+ba(c+ba)*bc)*(b+ba+ba(c+ba)*(c+ba))