[Solved]: Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

Problem Detail: 

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic pushdown automaton.

Now Assume that $R$ is a regular language and $D$ is a deterministic context-free language.
How can we prove that $R\cup D$ is a DCFL?

Note : I saw a similiar theorem for the intersection. But i'm new to PDA's and i almost have no idea how to prove this one.

Thanks in advance.

Asked By : Arman Malekzade

Answered By : Hendrik Jan

Yes, deterministic context-free languages are closed under union with regular languages.

It is easy to show they are closed under intersection with regular languages. We can apply a product construction. When reading a symbol we also do a step of a FSA that is running in parallel. Accepting a computation means accepting both the DPDA part and the FSA part.

This doesn't work for union. Why? Because a DPDA may end up in an infinite loop of $\varepsilon$-transitions, so it will never read all of its input. In that way we cannot test acceptance by the FSA.

In order to make this work we also need a normal form for DPDA, that they will never do such infinite loops, and always read all input. That normal form is usually proved when showing DCFL are closed under complement (and is non-trivial).

By he way, once we know that DCFL is closed under complement and closed under intersection with regular languages, closure under union with regular languages follows by De Morgan: $L\cup R = (L^c \cap R^c)^c$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58019