Search code examples
regexgrammarnfa

a*b* and (ab)* same or not?

are a*b* and (ab)* the same language? I am trying to make nfa for a*b*

Solution

  • These two regular expressions define different languages.

    a*b* matches any number of repetitions (including zero) of a followed by any number of repetitions (including zero) of b. For example aaabb.

    (ab)* matches any number of repetitions (including zero) of the ab sequence, for example abab.

    The empty string and ab are the only two words that match both regular expressions.