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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+22 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)$

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

0

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

+8

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

+8

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

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

So C Is true.

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

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.

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,999 questions

45,495 answers

131,568 comments

48,630 users