The Gateway to Computer Science Excellence
+1 vote

Given that:

  1. { A^m B^n C^k/ if (k=even) then m=n}
  2. { A^m B^n C^k/ if (n=even) then m=k}

Which of the above languages are DCFL?


According to me it is CFL as we have to first count k and then compare other inputs.. same for second language… but the answer given is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?

in Theory of Computation by Active (1.7k points) | 224 views
Let's check for first

{${a^mb^nc^k|if \;k=even \;then\;  m=n}$}

we can write this as

{$a^nb^nc^{2i}|i,n>=0$}$\cup$ {$a^jb^kc^{2i+1}|i,j,>=0$} we can clearly see that L1 is DCFL ,we can write like this also  for 2nd ,so both are DCFL

@Prateek Raghuvanshi so you have considered union of two DCFL as DCFL ?? or is it about deterministic children ??

Actually we can design dpda ,as we can see in second part of union there is no comparison and in first one there is comparison so design dpda for first one and for second one just skip all .this can be done by dpda .
Hello, But Union of 2 DCFL is  not DCFL.
 According to you how in same state we can push or  pop for input as well as just read and skip for that also ?
Dcfl under union is not closed ,it doesn't mean that it never be dcfl right. It means that union of dcfl may or may not dcfl but in this case it is dcfl .I will show you dpda

Dpda for second language-

why it is CFL but not DCFL ?

i mean what you people make to say it is not DCFL?

I tried for 1. 

@Prateek Raghuvanshi

can you please check..

@s ram

P: k is even

Q: m=n

Given, P->Q which can also be written as


So now we can check for the number of A's and B's and depending on their inequality we can take decision.

If unequal i.e. Q'=T we have to ensure P' is T I.e. C's are odd.

Else if equal then C's can be anything


assume it is L$, then it is just like

push a's for each a, pop a for each b,

if more b's than a, then just push b on to the stack.

       on k just changes the states ( even = one state and odd for another state )

     if $ appear on even state, go to reject !

     else $ appear on odd state, accept it !

else accept ( i mean number of a's = number of b's then no need to check k's even or not, but take care of dead conditions. )


EDIT :- i hope you also did the same !


@MiNiPanda Nicely explained.. actually solving recursively i was messed up somehow.. and could not build DPDA hence got confused. but now all is as clear as class...Thank u... @MiNiPanda @Prateek Raghuvanshi


@Shaik Masthan

more or less yes ...


@MiNiPanda yes your dpda is correct but From A to B there should be one more transition b,z/z .

Please log in or register to answer this question.

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,737 questions
57,388 answers
105,414 users