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?

- $G$ is not ambiguous
- There exist $x, y \in L(G)$ such that $xy \notin L(G)$
- There is a deterministic pushdown automaton that accepts $L(G)$
- We can find a deterministic finite state automaton that accepts $L(G)$

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\}$

+2

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

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

+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 $() , ()(), (()), (()()()).$

- $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 - Concatenation of two balance parenthesis will be balanced also . eq. $x = (()) \ y= () \ xy= (())()$.
- We can design Deterministic PDA for L. put left parenthesis (only) in stack and pop with right parenthesis.
- We cannot design DFA for L because we need a stack to match left parenthesis with right parenthesis.

only option**C**is true.

+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?

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

+17

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

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 {a^{n} b^{n} |n>=0} is not in reject state

got it :)

+14

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

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

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

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

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

0

@Hemant Parihar i m not getting

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

+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 (a^{n}b^{n})^{*}, We can't count a^{n}b^{n }using DFA. This is false.

So C Is true.

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

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.

+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-----> **S**S

S-----> a**S**bS

S------> aa**S**bbS

S-------> aabb**S**

** ** S--------> aabba**S**b

S---------> *aabbab*

C)-------->** L(G) = {a ^{n}b^{n }| 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) = {a^{n}b^{n }| 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 ---

52,218 questions

59,876 answers

201,074 comments

118,121 users