2,023 views
2 votes
2 votes

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?

3 Answers

1 votes
1 votes

$L_{1} = a^{m}b^{m}c^{2k} \cup a^{i}b^{j}c^{2k+1}$

The first part is DCFL and the second part is regular. Union of those two becomes DCFL (https://www.geeksforgeeks.org/union-and-intersection-of-regular-languages-with-cfl/).

$L_{2} = a^{m}b^{2n}c^{m} \cup a^{i}b^{2n+1}c^{j}$

Same as $L_{1}$, the first part is DCFL, and the second part is regular. Union of those two becomes DCFL.

0 votes
0 votes

I think we can approach it this way.

1 .First push all A's  and then pop one A for each B.If n>m then push B's after popping all A's. Then next check whether k is even or not by pushing and popping C's alternatively. If we are left with any C on top of stack(tos) after giving complete input, then we need not care about the m=n condition as k is not even.

Else if we are left with no C on tos then that means we have k as even. Now just check do we have any A's or B's. If stack is empty then we accept else reject. So it's a DCFL.

2. Similarly we can also do the 2nd one.

edited by
0 votes
0 votes
Just to add to @Joyoshish Saha’s answer.

The union of  a regular language and a DCFL is a DCFL. Let the states of the regular language be R and the states of the DPDA be D. Take the product automaton R $\times$ D and add the transitions of the NFA to the product automaton. The result would be another DPDA.

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
2 answers
2
ggwon asked Dec 29, 2022
701 views
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$}Is the above language DCFL or CFL ?
1 votes
1 votes
2 answers
3
vishal8492 asked Dec 2, 2016
1,373 views
Isn't WxWr DCFL as X acts as marker so DCFL should be right choice , why is it categorized as CFL and not DCFL?
3 votes
3 votes
2 answers
4