Which of the following statements is false?
2015
Which of the following statements is false?
- A.
Top-down parsers are LL parsers where first L stands for left-to-right scan and second L stands for a leftmost derivation
- B.
(000)* is a regular expression that matches only strings containing an odd number of zeroes, including the empty string
- C.
Bottom-up parsers are in the LR family, where L stands for left-to-right scan and R stands for rightmost derivation(in reverse)
- D.
The class of context-free languages is closed under reversal. That is, if L is any context-free language, then the language LR = {wᴿ : w ∈ L} is context-free
- E.
b and c
Attempted by 60 students.
Show answer & explanation
Correct answer: B
The correct answer is B.
Here is a breakdown of why each statement is true or false:
A is True: In LL parsers (top-down), the first "L" stands for scanning the input from Left to right, and the second "L" stands for producing a Leftmost derivation.
B is False: The regular expression (000)^* matches strings whose length is a multiple of 3 (e.g., epsilon, 000, 000000, 000000000). This includes strings with an even number of zeroes (length 0, length 6, length 12) as well as an odd number of zeroes (length 3, length 9). Furthermore, the empty string (epsilon) has zero 0s, and 0 is an even number, not an odd one.
C is True: In LR parsers (bottom-up), the "L" stands for scanning from Left to right, and the "R" stands for constructing a Rightmost derivation (in reverse).
D is True: Context-free languages are indeed closed under reversal. If you have a context-free grammar for a language L, you can generate the grammar for L^R simply by reversing the symbols on the right-hand side of every production rule.
E is Incorrect: Because statement C is true, this combined option is invalid.
Therefore, Option B is the only false statement.
A video solution is available for this question — log in and enroll to watch it.