![]() | ![]() |
|
Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory |
![]() |
| LinkBack | Thread Tools | Display Modes |
September 20th, 2012, 10: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! |