Let L be a language over Sigma = {a, b}. Which of the following statements is…
1996
Let L be a language over Sigma = {a, b}. Which of the following statements is true?
- A.
L = {x | x has an equal number of a and b symbols} is regular
- B.
L = {a^n b^n | n >= 1} is regular
- C.
L = {x | x has more a symbols than b symbols} is regular
- D.
L = {a^m b^n | m >= 1, n >= 1} is regular
Attempted by 5 students.
Show answer & explanation
Correct answer: D
Options 1, 2, and 3 all require comparing unbounded counts of a and b symbols. Such count-comparison languages cannot be recognized by a finite automaton, so they are not regular. Option 4 is different: L = {a^m b^n | m >= 1, n >= 1} has one or more a symbols followed by one or more b symbols. This is exactly the regular expression aa*bb*, or equivalently a+ b+. Therefore, option 4 is the true statement.