Question

prove that any regular language L can be represented by a regular expression in DNF(a1Ua2U...Uan), where none of ai, 1<=i<=n, contains the operator U.

Answer 1

The proof for such questions can be done by using structural induction-

Let T be an operator that takes in a regular expression and it returns an equivalent regular expression in DNF.

Base Cases :

T[ϵ] = ϵ,

T[σ] = σ,

T[∅] = ∅

If r = s + t, then we define T[r] = T[s] + T[t]

Now, if r = st, then by induction we know that T[s] = s1 + s2 + s3 + .... sn and T[t] = t1 + t2 + .... tm, where + doesn't appear in any of si or tj. We thus define T[r] = ∑_1≤i≤n∑_1≤j≤m si tj.

Now, if r = s*, then by induction T[s] = s1 + s2 + .... + sn where + again doesn't appear in si. Thus T[r] = (s1* .... sn*)*

Thus by structural induction we show that for every regular language can be represented by a regular expression in DNF.