Consider the following grammar. S -> AB A -> a A -> BaB B -> bbA Which of the…
2014
Consider the following grammar.
S -> AB
A -> a
A -> BaB
B -> bbAWhich of the following statements is FALSE? , ISRO 2014
Answer: D. No string produced by this grammar has four consecutive b's — To identify the false statement, analyze the length and structure of strings generated by the grammar. First, determine string lengths. A generates 'a'…
- A.
The length of every string produced by this grammar is even
- B.
No string produced by this grammar has three consecutive a's
- C.
The length of substring produced by B is always odd
- D.
No string produced by this grammar has four consecutive b's
Attempted by 100 students.
Show answer & explanation
Correct answer: D
To identify the false statement, analyze the length and structure of strings generated by the grammar.
First, determine string lengths. A generates 'a' (length 1). B -> bbA implies if A is odd length, B is even + odd = odd. Then A -> BaB implies A is odd + 1 + odd = odd. Since S -> AB, the total length is odd + odd = even.
Next, check 'b' sequences. B -> bbA introduces two b's. Expanding A recursively (A -> BaB) can nest B productions, allowing for four consecutive b's (bbbb). This structural property helps identify incorrect statements regarding string constraints.
Explore the full course: Iocl Engineers Officers Grade A Paper 2