Consider the following grammar :
S → XY
X → Y aY ∣ a and Y → bbX Which of the following statements is/are true about the above grammar?
(a) Strings produced by the grammar can have a consecutive three 's.
(b) Every string produced by the grammar have a b alternate and .
(c) Every string produced by the grammar have a at least two 's. b
(d) Every string produced by the grammar have 's in multiple of 2.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. (c) and (d) only
Explanation
Y always adds bb, so the number of b's is even (d). The shortest string is a·bba = abba, so every string has at least two a's (c). Strings can have consecutive a's and b's are not alternating.
More Theory of Computation and Compilers questions
- Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing M machine ? G L(G) = ϕ (a) is a CFG with M M…
- For a statement L ⊆ Σ∗ A language is recursive if there exists M some turing machine . Which of the following conditions is satisfied for ω…
- Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider: (i) L(s) ⊆ L(r) and L(s) ⊆ L(t) (ii) L(r) ⊆ L(s) and L(s) ⊆…
- Consider the language L = {a^(nk) | k > 0}, where n is a fixed non-negative integer. The minimum number of states of a finite automaton acc…
- The number of substrings that can be formed from a string given by a d e f b g h n m p is
- Consider the languages L₁ = {x | for some y with |y| = 2|x|, xy ∈ L} and L₂ = {x | for some y with |x| = |y|, xy ∈ L}, where L is a regular…