609 views

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 ?

1. Both $L_{1}$ and $L_{2}$ are not deterministic.
2. $L_{1}$ is not deterministic and $L_{2}$ is deterministic.
3. $L_{1}$ is deterministic and $L_{2}$ is not deterministic.
4. Both $L_{1}$ and $L_{2}$ are deterministic.

edited | 609 views
0
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

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...
by Boss (25.5k points)
selected by
0

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

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