Monday, March 06, 2017
why are regular expressions defined the way they are
BILL: The best way to prove closure properties of regular languages is to first prove the equiv of DFA's, NDFA's and Reg Expressions. Then, if you want to prove a closure property, choose the definition of regular that makes it easiest. For example, to prove Reg Langs closed under intersection I would use DFA's, NOT Reg Expressions.
STUDENT: I thought reg expressions were
a) finite sets
b) if alpha and beta are reg exp then so are alpha UNION beta, alpha INTERSECT beta, alpha CONCAT beta and alpha*
BILL: No. Regular expressions are defined just using UNION, CONCAT, and *.
STUDENT: Why? Had the defined it my way then closure under INTERSECTION would be easier. For that matter toss in COMPLIMENTATION and you're get that easily also.
BILL: First off, thats not quite right. You compliment a DFA by saying how lovely its states are. I think you mean complement. Second off, GOOD question!- Why are Reg Expressions defined the way they are. I"ll try to look that up and if I can't find anything I'll blog about it.
STUDENT: When will you blog about it?
BILL: I just did. Now, let me ask the question more directly:
The definition of Reg Exp is essentially closure under UNION, CONCAT, STAR. Why not other things? There are very broadly three possibilities:
a) Historical Accident.
b) Some good math or CS reason for it.
c) Something else I haven't thought of.
I hope its (b). Moreover, I hope one of my readers knows and can enlighten me and the other readers.