edited by
17,391 views
64 votes
64 votes

Let $G=\left(\left\{S\right\}, \left\{a,b\right\},R,S\right)$ be a context free grammar where the rule set R is $S \to a S b \mid S S \mid \epsilon$

Which of the following statements is true?

  1. $G$ is not ambiguous
  2. There exist $x, y \in L(G)$ such that $xy \notin 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)$
edited by

4 Answers

Best answer
99 votes
99 votes

It will be easy to analyze the problem if we replace terminal $a$ and $b$ by ( and ) respectively.

$S \rightarrow (S) \mid SS \mid \epsilon$ 

$L(G) =$ balanced parentheses  [each left parenthesis has a matching right parenthesis and are well nested ]

example $() , ()(), (()), (()()()).$

  1. $S \Rightarrow (S) \Rightarrow  ()$                                         
    $S \Rightarrow SS \Rightarrow  S \Rightarrow (S) \Rightarrow ()$      
    $S \Rightarrow SS \Rightarrow S \Rightarrow (S) \Rightarrow ()$
    String $()$ can be derived by above three way each having different derivation tree.
    So $G$ is Ambiguous
  2. Concatenation of  two balance parenthesis will be balanced also . eq. $x = (()) \ y= () \  xy= (())()$.
  3. We can design Deterministic PDA for L.  put left parenthesis (only) in stack and pop with right parenthesis.
  4. We cannot design DFA for L because we need a stack to match left parenthesis with right parenthesis. 

    only option C is true.
edited by
14 votes
14 votes

A) Not True. We can prove this is ambigious by deriving epsilon by two derivations.

S-> ϵ

S->SS , SS-> Sϵ, S-> ϵ

B) Due to S->SS this is false.

D) Language given is like (anbn)*, We can't count anbusing DFA. This is false.

So C Is true.

7 votes
7 votes
a) is not possible we can make two parse tree.

b) is not correct let take x = aabb and y = ab then xy = aabbab we can produce it by
S->SS {take one S for x and one for y}

c) true -------->   For this one no. of a = = b we can determine pushdown automata as we can push for a and pop for b.

d) not possible memory require to count a for number of b.
1 votes
1 votes

C ) Is the Answer.

A- Incorrect we get two parse trees for string – aabb ..there may be many as well.

B- take x – ab, y – abab, xy= ababab. This will also belong to L(G).

D – Incorrect Given as context free..we will require storage to accept strings produced by this language.


Ps..  please correct if my reasoning is not valid.

Answer:

Related questions

61 votes
61 votes
7 answers
3
Kathleen asked Sep 17, 2014
14,797 views
Consider the following deterministic finite state automaton $M$.Let $S$ denote the set of seven bit binary strings in which the first, the fourth, and the last bits are $...