What is the language expressed by these expressions and why aren't they equal?
Asked
Active
Viewed 421 times
1 Answers
3
L1 = (ab)* stands for ab repeated 0 or more times.
L2 = a*b* stands for a repeated 0 or more times followed by b repeated 0 or more times.
Those languages aren't equal because word abab is in language L1 but it's not in language L2.
Those languages aren't equal because word a is in language L2 but it's not in language L1.
There is a very useful service web service used for comparing regular expressions. Once you type in the regular expression, it describes it and let's you test it.
Examples of words in those languages:
L1:
- ""
- "ab"
- "abab"
- "ababab"
L2:
- ""
- "a"
- "aa"
- "bbbb"
- "ab"
- "aaaabbbbbbb"
xenteros
- 15,586
- 12
- 56
- 91
-
@SoumyaPawar no. The other is just `a`s followed by `b`s. – xenteros Jul 30 '17 at 15:54
-
(ab)*={€,ab,abab,....} a*b*={€,a,aa,bb,ab, abab, ...} aren't the strings accepted by both languages same? Won't abab,ababab be accepted by a*b* too? If not, why? Thanks – Soumya Pawar Jul 30 '17 at 15:55
-
@SoumyaPawar look how I described those languages and look at the examples – xenteros Jul 30 '17 at 15:57
-
@SoumyaPawar look, single letter `a` is a word in `L2` and isn't a word in `L1`. – xenteros Jul 30 '17 at 16:01