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

<p>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.</p>

CC BY-SA 3.0
2016-06-01T11:11:03.647Z
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.
Kaveh
CC BY-SA 3.0
2016-06-01T11:30:31.057Z
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.
Jeffrey Shallit
CC BY-SA 3.0
2016-06-01T12:15:49.417Z
You can click on `edited` below the question for edit history. The original version is [here](http://cstheory.stackexchange.com/revisions/34862/1). My take is that the author didn't know if the union of two DCFLs would be inside CFL, otherwise why ask if it is CSL or RE.
Kaveh
CC BY-SA 3.0
2016-06-01T12:36:52.093Z
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.
Jeffrey Shallit
CC BY-SA 3.0
2016-06-01T13:04:23.047Z
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.
Lev Reyzin
CC BY-SA 3.0
2016-06-01T13:07:51.637Z
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.
Kaveh
CC BY-SA 3.0
2016-06-01T10:28:33.363Z
2016-06-01T13:05:00.457Z
2016-06-01T13:05:00.457Z
Jeffrey Shallit
<p>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. </p>

CC BY-SA 3.0
2016-05-31T03:09:49.193Z
OK, I was unaware about that ,will take care now !
govindkt2395
CC BY-SA 3.0
2016-05-30T16:11:49.680Z
2016-05-30T16:11:49.680Z
govindkt2395
<p>We know that DCFL is not closed under the union operation and
CFL is closed under union and contains the union of DCFLs.</p>

<p>Is there a characterization of finite unions of DCFLs?</p>

<fl.formal-languages><automata-theory>
Characterization of union of DCFLs
Muktinath Vishwakarma
# Characterization of union of DCFLs

(Asked by: username_0 on 2016-05-30)

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?

**Tags:** fl.formal-languages, automata-theory


---

## 2 answers

### Answer by username_1 on 2016-06-01. Score: 7

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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: 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.  
> **username_2**: You can click on `edited` below the question for edit history. The original version is [here](http://cstheory.stackexchange.com/revisions/34862/1). My take is that the author didn't know if the union of two DCFLs would be inside CFL, otherwise why ask if it is CSL or RE.  
> **username_1**: 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.  
> **username_3**: 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.  
> **username_2**: 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.  

---

### Answer by username_4 on 2016-05-30. Score: -1

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.

> **Comments:**
> **username_4**: OK, I was unaware about that ,will take care now !  

---

