Search code examples
algorithmregular-language

is a* the same as (a*)*?

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.

Solution

  • 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.