The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.8k views

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)$
asked in Theory of Computation by Veteran (69k points)
edited by | 1.8k views

4 Answers

+36 votes
Best answer

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.
answered by Veteran (55.2k points)
edited by
but sir in (D) it is telling about a DFA, and it is possible to design (ab)*

We can say (C) is more appropriate. right?

@srestha "We can find a deterministic finite state automaton that accepts L(G)"

Obviously this should mean the DFA must reject any string not in L(G). 

@srestha , No it is not (ab)*, it is more than that. it also includes the strings as , aabb, aaabbb, ...

or abaabb, abaaabbb, ..... or aabbab , aaabbbab, ....

$L_1 = \{(ab)^n\;|n \geq 0\}$

$L_2 = \{a^nb^n\;|n \geq 0\}$

$L = \{L_1 \cup L_2\}^*$

yes other than accepting state all other should be in reject state

but here {an bn |n>=0} is not in reject state

got it :)

Language Description:  

L = { w $\in$ {a, b}*  : $n_{a}$ (w) = $n_{b}$ (w) and $n_{a}$ (v) >= $n_{b}$ (v), 
                                 where v is any prefix of w }
 

@Hemant can you explain how is it true for the strings ba, baab as these are not accepted by the language itself ?
@just_bhavana The strings ba, baab are not present in the language. Why are you checking for these strings?

Check for those strings that are present in the language, you will find the above property always holds for them.

but here {an bn |n>=0} is not in reject state

srestha explain this pls

+8 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.

answered by Veteran (49.5k points)

can anyone explain how it is like (anbn)*. ????

Because i am able to derive abb, which does n't fall under (anbn)*

check the selected answer.

but abb cannot be derived from this grammar, you might have done some mistake
aababb can be generated through the given grammar but it is not in form of (anbn)*   ????
+6 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.
answered by Loyal (3.7k points)
option b if x=a y=a cannot be accepted i.e. aa is not acceptedd ..m i correct?
@Himanshu but neither a nor b is generated by the given grammar.
+3 votes

A ------> G is not ambiguous because we can derive a same string from 2 different parse trees.

B) ------> consider x= aabb and y= ab and x,y ∈L(G), now xy= aabbab ab ∈L(G)

as S-----> SS

     S-----> aSbS

    S------> aaSbbS

​​​​​​​     S-------> aabbS

​​​​​​​     S--------> aabbaSb

​​​​​​​     S---------> aabbab

C)--------> L(G) = {anb| n>=0} because in given grammar - S→aSb∣SS∣ϵ, 

this S→aSb means generating equal no of a's and b's and SS→SS has no effect on equal no of a's and b's, because SS is both variables and ultimately you always will end up with equal no of a's and b's.

Also, L(G) = {anb| n>=0} is DCFL and not regular because in order to do compare a's and b's we need memory element and DFA cannot do that.

Moreover, DPDA for L(G) is ---

answered by Veteran (20k points)
edited by
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
114,176 comments
38,664 users