UGC NET CSE | December 2015 | Part 3 | Question: 28

Question

Given the following two languages:

• $L_1=\{a^nba^n\;|\;n>0\}$
• $L_2=\{a^nba^nb^{n+1}\;|\;n>0\}$

Which of the following is correct?

• A.  $L_1$ is context free language and $L_2$ is not context free language
• B.  $L_1$ is not context free language and $L_2$ is context free language
• C.  Both $L_1$ and $L_2$ are context free languages
• D.  Both $L_1$ and $L_2$ are not context free languages

Answer 1

Answer : A

A. L1 is context free language (deterministic) and L2 is not context free language

For L1, we need to count the number of a's before and after 'b' and this length is not finite. Hence, it is DCFL and not regular.

For L2, in addition to above comparison, we also need to ensure number of b's following the a's is just one more. This is a second non-finite comparison and cannot be done with just one stack. So, this makes L2 a CSL.

Comments

@shekhar How you analysing L1 and L2 ? Can you expalin them ?

---

In first case we push all the strings on to the stack when we see a b we make a transition on next state and keep on popi off all the a and at the end there will be $ in the bottom of stack and we will accept that string.

I think this is DCFL

in second case on half way we can do it but late on there is nothing to compare against b^n. So it is not CFL.

This is what i thought .What do you think Am i right or wrong .?

If you have something to say please share it...

---

<In first case by which symbol you are poping all a,s >

---

we have a^n b a^n

so push all a's first don't do anything with b then pop all a because both a's are same.

---

Is the given language is regular ?

---

Not at all .We can't store infinite string in finite memory.

Answer 2

$L_1=\{a^nba^n\;|\; n>0\}$ is CFL

push $a's$ in stack ,do nothing with $b$ , then pop $a's$ from stack on reading $a's$

$L_2=\{a^nba^nb^{n+1}\;|\; n>0\}$ is CSL.

Push $a's$ in stack, donothing on $b$ , pop $a's$ from stack on reading $a's$, then we left with $b's$ with empty stack, then we can't ensure these $b's$ are one more that earlier $a's$.

Option $A$, $L_1$ is context free and $L_2$ is not context free language.

Answer 3

l1 :is language for which we cant write regular expression and it need stack  for comparison  so it is CFL
l2 eg: a^3ba^3b^4
first push all three a's in stack than when b comes pop all upconing a's with those a's which are present in stack ..now at this point one comparison is over..now 4 b''ss comes neglect them or we can say do thing with them so we left with empty stack so it is also CFL..
so (c) option