We know that DCFL is not closed under the union operation and CFL is closed under union and contains the union of DCFLs.

Is there a characterization of finite unions of DCFLs?


One direction is clear: the union of any finite number of DCFL's is a CFL.

However, a precise characterization of the union-closure of DCFL's was not obvious to me at all (and I teach this stuff and wrote a book on it), so I went searching with a google search. I found this paper by my colleagues Martin Kutrib and Andreas Malcher: Context-Dependent Nondeterminism for Pushdown Automata, O.H. Ibarra and Z. Dang (Eds.): DLT 2006, LNCS 4036, pp. 133–144, 2006. Theorem 1 gives a characterization of this class.

  • $\begingroup$ I think the question as it was phrased originally was clearly off-topic (it was asking if union of DCFLs is in CFL or CSL or RE) and could be answered by an undergraduate who has taken an automata theory course, so imo the close votes were justified. I think a better way to deal with this kind of situation where a better research-level question exists is to edit the question to make it a research-level question when you think it should not be closed rather than saying the question as originally phrased is on-topic and the close votes were not justified. $\endgroup$ – Kaveh Jun 1 '16 at 11:11
  • 3
    $\begingroup$ I don't think that's a completely accurate representation of the original question (but I can't figure out how to see the original question). It first asked, what are the unions of DCFL's and then said, is it CFL or CSL or RE. A reasonable interpretation of the question is: is the class of finite unions of DCFL's equal to CFL? I stand by my original assessment: some are too quick to vote "off-topic". I've seen it a number of times now. $\endgroup$ – Jeffrey Shallit Jun 1 '16 at 11:30
  • 2
    $\begingroup$ So what if he/she didn't? The question about whether it's equal to CFL is (a) nontrivial and (b) a subject of real research. Be more charitable. $\endgroup$ – Jeffrey Shallit Jun 1 '16 at 12:36
  • 1
    $\begingroup$ May I point out that this question was never closed. Rather, It was downvoted, probably for being poorly phrased. Moreover, I will edit this answer to remove the commentary unrelated to the question's content. $\endgroup$ – Lev Reyzin Jun 1 '16 at 13:04
  • 2
    $\begingroup$ I am not trying to argue, I agree that we sometimes close questions as off-topic which can have a more charitable on-topic interpretation, I am just explaining how I read the question (is the union of two DCFLs a CFL? which I think is a fair interpretation) and why I personally voted to close as off-topic and think it was justified. My view is that when you see a question being closed and you think there is a good interpretation that people are missing, edit the question to make the good interpretation known to others and they will hopefully retract their close/down votes. $\endgroup$ – Kaveh Jun 1 '16 at 13:07

DCFLs not closed under union hence we will see language higher than DCFLs in Chomsky's classification hierarchy CFLs are closed under union hence union of two DCFL if not DCFL then CFL you can take the example of a^nb^n and a^2n b^n.

  • $\begingroup$ OK, I was unaware about that ,will take care now ! $\endgroup$ – govindkt2395 May 31 '16 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.