The Gateway to Computer Science Excellence
+4 votes
310 views

$L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$

$L_2=\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$

Which of the following is True?

(a) $L_1$ is CFL, $L_2$ are DCFL                    (b) $L_1$ is DCFL, $L_2$ is CFL 

(c) Both $L_1$, $L_2$ are CFLs                       (d) Both $L_1$, $L_2$ are DCFLS

in Theory of Computation by Junior (541 points)
edited by | 310 views
0
But L2 is not DCFL, it is ncfl actually.
0
But Sir a^nb^m |m>n or m<n is DCFL,and adding c^k will make it NDCFL?
0
Yes, you are right, missed that k is not in condition

1 Answer

+8 votes
Best answer

Yes $L_2 =\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ is DCFL 

having DPDA

 

$L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ is also DCFL 

having DPDA 

by Veteran (56.6k points)
selected by
0
Sir , how  L2 is DCFL ?? I think it is NDCFL bcoz m>n or m<n
0
push a and for every a pop b , we have to do it for every language... i think there is no ambiguity na  here. so DCFL .
0
ok got it sir
0
I think here m is != n and therefore, it is dcfl.
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,666 questions
56,154 answers
193,758 comments
93,723 users