The Gateway to Computer Science Excellence
+35 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)$
in Theory of Computation by Veteran
edited by | 4.7k views
It's $L= \{w\epsilon\{a,b\}^*: n_a(w)=n_b(w) and n_a(v)>=n_b(v), where \ v \ is \ any \ prefix \ of\ w\}$

If you couldn't make the connection to balanced parentheses, here's how you could solve it:

  1. Eliminate option D because if D were true, then C would have to be true as well, since every DFA is also a DPDA (that just leaves its stack untouched)
  2. Eliminate option B. Since the grammar has the derivation S → SS, any two strings in the grammar could be concatenated and the resulting string would still be generated by the grammar (if S $\rightarrow$ x and S $\rightarrow$ y, then S $\rightarrow$ SS $\rightarrow$ xy).
  3. Eliminating option A is trivial (2 leftmost derivations for ab: S $\rightarrow$ SS $\rightarrow$ aSbS $\rightarrow$abS $\rightarrow$ab and S $\rightarrow$ aSb $\rightarrow$ab)

The question reads "Which of the following statements is true?"

Can anyone please describe the language generated by the grammar in terms of a and b, I get it with () analogy, but please describe your approach if you didn't know that.

4 Answers

+61 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.
by Veteran
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

sir how will (ab)* can produce aabb, aaabbb, ...

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

it can produce only ab,abab,ababab ....plz correct me if i m wrong
rohit our language is ((ab)^n∪(a^nb^n))* not only (ab)* all the comments of saini sir carefully
@hemant sir very nice point
@Hemant A/c to u string like ba, baaabb are in the language ??

The grammar is ambiguous not because a string generated by it has more than one derivations (here, 3).

It is ambiguous because that string has more than one leftmost (or rightmost) derivations (only 2).


@Hemant Parihar i m not getting 

na(v) >= nb​ (v), where v is any prefix of w ...please explain more..

Option b is indirectly saying that given language is not closed under concatenation...
But since the given language is context free, it is closed under concatenation.

hence option b is false.

One more reason to eliminate option B :)
+12 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.

by Boss

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)*   ????
+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.
by Active
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.

@Arpit [email protected]

If we take $x=ab$ and $y=aabb$.

then $xy=abaabb$ (which is not in language ).

Why $B)$ is false?


@Karan Dodwani 1

from your example, B will be false here 

x = ab  and y = aabb ,so xy = abaabb

xy ϵ L(G) can be prove from this -:

S-> SS



   ->(ab)(aabb)        // i have used brackets for explaination.

we can generate:
aaabbabb which is not in the form of (a^n b^n)*
+4 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 ---

by Loyal
edited by
@ iarnav

What i think is that...there is a difference between L(G)= {a^nb^n | n>=0} and language having equal no. of a's & b's, because here a & b can be in ny order only there number of occurrence matters.

please,correct me if i am wrong.

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
52,218 questions
59,876 answers
118,121 users