The Gateway to Computer Science Excellence
+2 votes
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. 
in Theory of Computation by Boss (30.1k points)
edited by | 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

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

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.
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.
by (67 points)

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
50,648 questions
56,430 answers
195,208 comments
99,922 users