My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Reply
 
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( ( )).
bhargav k is offline  
 

My Computer Forum is free to register and we welcome everyone!

Reply

  My Computer Forum > Computer Science Forum > Theory of Computation

Tags
problem, solving



Thread Tools
Display Modes






Copyright © 2017 My Computer Forum Forum. All rights reserved.