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.
- D.
The class of context-free languages is closed under reversal. That is, if L is any context-free language, then the language
\(L^R =\{w^R: w \varepsilon L\}\)is context-free.
Attempted by 58 students.
Show answer & explanation
Correct answer: B
The false statement is: (000)* is a regular expression that matches only strings containing an odd number of zeroes, including the empty string.
Why this is false: (000)* matches strings formed by concatenating zero or more copies of the substring "000". Therefore it accepts strings whose number of zeros is a multiple of 3 (including the empty string). Multiples of 3 are not the same as odd numbers. For example, the empty string is matched by (000)* but has zero zeros (an even number), and the string "0" (one zero) is not matched by (000)* but has an odd count.
Correct regex for an odd positive number of zeros: (00)*0. This produces 2k zeros from (00)* plus one more zero, giving 2k+1 zeros (odd). This does not include the empty string; including the empty string would contradict the requirement of odd count.
Why the other statements are true:
Top-down parsers: These are LL parsers. The first L means a left-to-right scan of the input, and the second L means the parser constructs a leftmost derivation.
Bottom-up parsers: These are in the LR family. The L indicates left-to-right scanning of the input, and the R indicates that the parser effectively builds a rightmost derivation in reverse (a rightmost derivation is recovered bottom-up).
Closure under reversal for context-free languages: Given a context-free grammar with productions A -> X1 X2 ... Xk, form a new grammar that has productions A -> Xk ... X2 X1 for every original production. The new grammar generates exactly the reversals of the strings generated by the original grammar, so context-free languages are closed under reversal.