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.
$\begingroup$ $\endgroup$
3 
- 2$\begingroup$ No. $(ab)^*$ does not contains $aa$ (it only contains $\varepsilon, ab, abab, ababab,...$), whereas $(a+b)^*$ does. $\endgroup$plshelp– plshelp2020-10-11 05:57:38 +00:00Commented Oct 11, 2020 at 5:57
- 1$\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– greybeard2020-10-11 11:19:05 +00:00Commented Oct 11, 2020 at 11:19
- $\begingroup$ Simpler, $(ab)^*$ does not contain $a$. $\endgroup$user16034– user160342023-08-24 08:49:57 +00:00Commented Aug 24, 2023 at 8:49
Add a comment |
3 Answers
$\begingroup$ $\endgroup$
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)^*]$.
$\begingroup$ $\endgroup$
No, $(ab)^*=\{\epsilon,ab,abab,abababa\cdots\}$. The length is always even.
$\begingroup$ $\endgroup$
2 No, they are not equal but (a+b)* and (a*b*)* are equal.
- $\begingroup$ Are you sure about what you wrote ?? $\endgroup$user16034– user160342023-08-24 08:48:45 +00:00Commented Aug 24, 2023 at 8:48
- 1$\begingroup$ @YvesDaoust Some of the *'s in the answer were interpreted as the emphasis notation in markdown. I've edited it to what seems to be the intention. $\endgroup$2023-08-24 10:21:40 +00:00Commented Aug 24, 2023 at 10:21