+27 votes
3.4k 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)$

edited | 3.4k views
0
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\}$
0

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)
0

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

## 4 Answers

+50 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 (56.4k points)
edited by
+1
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?
+2

@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).

+13
@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\}^*$
+1

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 :)

+10

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 }

0
@Hemant can you explain how is it true for the strings ba, baab as these are not accepted by the language itself ?
+1
@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.
0

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

srestha explain this pls

0
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
0
rohit our language is ((ab)^n∪(a^nb^n))* not only (ab)*...read all the comments of saini sir carefully
0
@hemant sir very nice point
0
@Hemant A/c to u string like ba, baaabb are in the language ??
0

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).

+9 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 (41.1k points)
0

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

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

+2
check the selected answer.

but abb cannot be derived from this grammar, you might have done some mistake
0
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 (3.8k points)
0
option b if x=a y=a cannot be accepted i.e. aa is not acceptedd ..m i correct?
0
@Himanshu but neither a nor b is generated by the given grammar.
0

@Arpit [email protected]

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

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

Why $B)$ is false?

0

@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

->(aSb)(aSb)

->(ab)(a(aSb)b)

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

+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 (8k points)
edited by
0
@ 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.
Answer: