5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ $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. $\endgroup$
    – user19121278
    Jun 22, 2022 at 22:16
  • 1
    $\begingroup$ @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! $\endgroup$
    – Hendrik Jan
    Jun 23, 2022 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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