Are the languages of the following regular expressions the same?

(ab)*

a*b*

Question

Are the languages of the following regular expressions the same?

(ab)*

a*b*

BlackTom AI · Accepted Answer

We need to compare the languages of two regular expressions and decide if they are the same.
Option True: The claim that the languages are the same. Think about what (ab)* generates. This expression repeats the exact substring 'ab' any number of times, including zero times. Therefore the strings produced are: ε, ab, abab, ababab, ..., i.e., any number of consecutive 'ab' blocks with no other characters, and nothing like 'a' or 'b' alone, or 'aa', or 'abb', etc. On the other hand, a*b* describes strings consisting of zero or more a's followed by zero or more b's, in that order. This includes ε, a, aa, aaa, b, bb, ab, aab, aaabb, and so on, as long as all a's come before any b's. Since (ab)* restricts to alternating blocks of 'ab' with no lone 'a' or 'b' and no concatenation of 'a's before 'b's except in the exact pair 'ab', the two languages are clearly not identical. Therefore the statement that they are the same is incorrect.
Option False: The claim that the languages are not the same. This aligns with the observations above: (ab)* yields strings only of the form (ab)^n, which are exactly the empty string and repeated 'ab' blocks, while a*b* yields a broader set where a's can appear before b's in any quantity, including cases like 'a', 'aa', 'b', 'ab', or '' (epsilon). Because these sets do not match, this option correctly reflects that the languages are different.
In summary, the first option asserts equality (which fails due to the structural restrictions of each language), while the second option asserts inequality (which matches the actual languages described by the two expressions).

COMP30026_2025_SM2 2025 sample exam - Requires Respondus LockDown Browser

Are the languages of the following regular expressions the same? (ab)* ab

查看解析

登录即可查看完整答案

类似问题

Question at position 22 Which of the following strings match(es) the regular expression in following command? grep “^[ABCa-z][23]” Notes.TXT ABCa-z2345x22345Ba32ABCAll of these.