3

Quick question, if a is a regular expression then is it true that a* = (a*)* ?

Is (a*)* a valid expression? If it is, then can anyone explain why is it the same as a*? I apologize for asking here, but I couldn't find anything via Google.

Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27
user1825415
  • 43
  • 4
  • 1
    Yes, they are the same (theoretically). – nhahtdh Dec 08 '12 at 17:00
  • I said that it is theoretically the same, but the code compiled by the regex engine may differ between them, and a* is more efficient than (a*)* in that case, since (a*)* will introduce another level of backtracking. – nhahtdh Dec 08 '12 at 17:12
  • @nhahtdh : Does Lex tool not optimized `(a*)*` to `a*`? Because minimization should work? – Grijesh Chauhan Dec 19 '12 at 15:40
  • @GrijeshChauhan: I don't know about Lex tool. Common regex engine will not do minimization. – nhahtdh Dec 19 '12 at 16:29

1 Answers1

7

Yes, a*=(a*)* are same. Both generate same language that is string any numbers a's including null.

L(a*) = {^, a, aa, aa...... } = L ((a*)*)

Is (a*)* a valid expression?

Yes, this expression is called REGULAR-EXPRESSION (I saw you missed the tag). Any Regular Language(RL) can be represented by Regular Expression(RE). A alphabetical way of represent RL.

why is it the same?

* means repetition any numbers of time (including 0 times).

a* means 0 a, 1 a, 2 a or any number of a.

(a*)* means repetition for all string in a* set for any number of time (including 0 times).

Because L(a*) means all string consists using a. its supper-set of every set consists of strings of a's. and L((a*)*) is same.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208