The Gateway to Computer Science Excellence
+2 votes

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. 
in Theory of Computation by
edited by | 785 views
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

2 Answers

+3 votes
Best answer
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...


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...
selected by


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.
0 votes
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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,517 answers
95,368 users