
Theory of Computation Theoretical Computer Science  Automata Theory, Computability Theory, and Computational Complexity Theory 
 LinkBack  Thread Tools  Display Modes 
September 20th, 2012, 09:50 AM  #1 
Joined: Sep 2012 Posts: 1  please!! Help in solving this problem
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(()). 
My Computer Forum is free to register and we welcome everyone! 