Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... }

I am new to Finite automata and this simple notion is confusing me!
I didn't find (a+b)* = (ab)* in rules of regular expressions.

  • 2
    $\begingroup$ No. $(ab)^*$ does not contains $aa$ (it only contains $\varepsilon, ab, abab, ababab,...$), whereas $(a+b)^*$ does. $\endgroup$ – plshelp Oct 11 '20 at 5:57
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Can you provide a reference for the two languages presented? (The second might have been denoted [ab]*.) $\endgroup$ – greybeard Oct 11 '20 at 11:19

The regular expressions $(a+b)^*$ and $(ab)^*$ represent languages according to the semantics of regular expressions. Formally, the language $L[r]$ corresponding to a regular expression $r$ is defined as follows:

  • $L[\emptyset] = \emptyset$.
  • $L[\epsilon] = \epsilon$.
  • $L[\sigma] = \sigma$ for $\sigma \in \Sigma$.
  • $L[r_1+r_2] = L[r_1] \cup L[r_2]$.
  • $L[r_1r_2] = L[r_1] L[r_2]$, where $L_1 L_2 = \{ w_1w_2 : w_1 \in L_1, w_2 \in L_2 \}$.
  • $L[r^*] = L[r]^*$, where $L^* = \bigcup_{n \geq 0} L^n$, and $L^n$ is defined recursively by $L^0 = \{\epsilon\}$ and $L^{n+1} = L^n L$.

Two languages over the same alphabet are equal if they are equal as sets, that is, if they contain the same words. In your case, you haven't specified the underlying alphabet $\Sigma$, so I'm assuming that $\Sigma = \{a,b\}$.

Now that you have all the definitions, you can check for yourself whether $L[(a+b)^*]$ equals $L[(ab)^*]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.