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?
@Prateek Raghuvanshi so you have considered union of two DCFL as DCFL ?? or is it about deterministic children ??
Dpda for second language-
I tried for 1.
can you please check..
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
more or less yes ...
@MiNiPanda yes your dpda is correct but From A to B there should be one more transition b,z/z .