UGC NET CSE | June 2014 | Part 3 | Question: 75

Question

Given the following two languages : 

$L_{1}=\left\{a^{n}b^{n}|n\geq 1\right\} \cup \left\{a\right\}$

$L_{2}=\left\{w C w^{R}|w \in \left\{a, b\right\}^{*}\right\}$

Which statement is correct ?

• A. Both $L_{1}$ and $L_{2}$ are not deterministic.
• B. $L_{1}$ is not deterministic and $L_{2}$ is deterministic.
• C. $L_{1}$ is deterministic and $L_{2}$ is not deterministic.
• D. Both $L_{1}$ and $L_{2}$ are deterministic. 

Comments

I think A is the answer.

L1 can be accepted by NPDA. // It is CFG

L2 can be accepeted by DPDA or NPDA // It is CFG

 

Correct me if I am wrong

Answer 1

Both are deterministic CFL

L2... Insert symbol into stack until C doesn't appear... If C the skip it and compare top of stack with input symbol.. Because of C it becomes deterministic...

L1..

If "a " comes then we can't decide ...but after "a"  , "a" or "b" comes then first part of given language is considered and if epsilon comes then second part need to consider... We can easily recognize it with the help of DPDA...

Comments

@papesh

What about union {a}  in L1 ?

I think answer should be (B).

Because, We know that deterministic CFL is not closed under Union.

Please Correct me if i m wrong.

---

I think you are correct. For L1 we will not able to give DCFL.So,option B is correct option.

Answer 2

L1 is NDCFL Languuage because for that we will not able to give DCFL but L2 is DCFL languaga.So,option (B) is the correct option.