The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
68 views

asked in Theory of Computation by Active (2.1k points) | 68 views
$L_2$ and $L_4$ are CFL. Also DCFL
plz explain in detail
Is it correct?
yes,plz explain each one in detail
$L_2$ has both conditions i<=j and j>=i so it does not matter just check j = k.

$L_4$ match i with j and if you get empty stack after all b finished then check c for even by alternating push and pop
in L3 and L4 single comparison is required where as in L1,L2 two comparison is required
explain L2?
l2 is not dcfl its cfl only

no l2 is dcfl...it can be simply implemented using single stack....and deterministic transition...

l2 is just representing aibjck  ,j=k  ???

Good question.

1 Answer

0 votes
$L_{2}$ and $L_{4}$ both are DCFL. So answer is 2.

In $L_{2}$ we have to only check j==k or not.
answered by Boss (8.5k points)


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

29,961 questions
37,633 answers
96,402 comments
35,286 users