# Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

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.

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.
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$.
• $L=\{a^mb^n∣m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗} =\{a^mb^n|m<n\} \cup \{a^mb^n|m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$. Here DCFL $\cup$ regular, but you never able to made DPDA For $L.$ Always you get a NPDA. So DCFL $\cup$ regular not always close. Commented Jun 22, 2022 at 22:16
• @user19121278 Your language is equal to $\{0,1\}^* \setminus \{a^nb^n \mid n\ge 0 \}$. It is well known that DCFL is closed under complement, so that would be a big surprise! Commented Jun 23, 2022 at 2:48