Multiple choice

Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S $\rightarrow$ a S b | S S | $\epsilon$ Which of the following statements is true?

  1. G is not ambiguous
  2. There exist x, y $\epsilon$ L(G) such that xy $\require{cancel} \cancel{\epsilon}$ L(G)

  3. There is a deterministic pushdown automaton that accepts L(G)

  4. We can find a deterministic finite state automaton that accepts L(G)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

(1) Incorrect since the production has same non terminal in both sides, so definitely ambiguous. (2) Since S $\rightarrow$ SS " this leads to conjunction of every possible string to make a valid string in L(G) . (3) Context free languages are accepted by push down automata so true. (4) The language is not regular so DFA is not possible.

Keep practicing — related questions