Question

a.) Exhibit an algorithm that, given any three regular languages, L,L1,L2, determines whether or not L = L1L2.

b.) Describe an algorithm by which one can decide whether two regular expressions are equivalent.

Answer 1

b) algorithm for testing the equivalence of regular expression.

Two regular expressions R, S ∈ R(Σ) are equivalent, denoted as R ∼= S, iff L[R] = L[S].

example

((R1 + R2) + R3) ∼= (R1 + (R2 + R3)),

((R1R2)R3) ∼= (R1(R2R3)),

(R1 + R2) ∼= (R2 + R1),

(R ∗R ∗ ) ∼= R ∗ ,

R ∗∗ ∼= R ∗ .

1. There is an algorithm to test the equivalence of regular expressions, but its complexity is exponential.

2. an algorithm uses the conversion of a regular expression to an NFA, and the subset construction for converting an NFA to a DFA.

3. Then the problem of deciding whether two regular expressions R and S are equivalent is reduced to testing whether two DFA D1 and D2 accept the same languages.

4. L(D1) − L(D2) = ∅ and L(D2) − L(D1) = ∅.

5.the equivalence problem for regular expressions reduces to the problem of testing whether a DFA D = (Q, Σ, δ, q0, F) accepts the empty language, which is equivalent to Qr ∩ F = ∅.