bhargav k

A regular expression is in disjunctive normal form (DNF for short) if it is of the form
1 [2 [ · · · [n for some n  1, where none of the terms i contains an occurrence of [.
Show that every regular language is represented by some regular expression in disjunctive
normal form.
Hints:
• Proceed by structural induction (or induction over the height of the expression tree):
Show first (as basis step) that the basic regular expressions a and ; have DNFs. Show
then (in the inductive step) that the composite regular expressions ,  [ , and 
have DNFs under the inductive hypothesis that  and (if applicable)  have such a
DNF.
• Use without proof the fact shown to some degree in class that L(( [ )) =
L(()).