Coursify

Closure Properties of Languages Accepted by Deterministic Pushdown Automata (DPDA)

Closure Properties of Languages Accepted by Deterministic Pushdown Automata (DPDA)

Verified Sources
Oct 9, 2026

A language accepted by deterministic pushdown automata (DPDA) is a Deterministic Context-Free Language (DCFL). For DCFLs, closure behavior differs sharply from general CFLs: DCFLs are closed under complement, but not under union (and therefore not under intersection either).2

Hence, for the options:

  • (i) Complement ✅
  • (ii) Union ❌
  • (iii) Both ❌
  • (iv) None of the above ❌

Correct answer: (i) Complement.

Key terms: DPDA , DCFL , closure property , complement.

Footnotes

  1. Deterministic pushdown automaton - Wikipedia - Notes closure: (effectively) closed under complementation but not under union. ↩

  2. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

DCFL closed under complement (and not under union)

Why complement works for DPDA/DCFL

Intuitively, if a DPDA can decide membership in LL deterministically, then it can be engineered to decide membership in L‾\overline{L} as well. Standard constructions (as in classic automata theory results) show that deterministic context-free languages are effectively closed under complementation, though the proof is technically delicate due to deterministic stack behavior and avoiding infinite computations.2

Why union fails for DPDA/DCFL

Although union is easy for nondeterministic PDA (and CFLs), it breaks determinism: given two deterministic machines for L1L_1 and L2L_2, a deterministic machine generally cannot combine them without requiring nondeterministic “choice” about which component language to follow—leading to a language outside the DCFL class. This is reflected in the known fact that DCFLs are not closed under union.2

Footnotes

  1. Deterministic pushdown automaton - Wikipedia - Notes closure: (effectively) closed under complementation but not under union. ↩

  2. Deterministic Context-Free Languages are Closed Under ... (outline) - Provides DPDA/DCFL complement construction idea. ↩

  3. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

  4. Deterministic Context-free Languages NOT Closed Under Union or Intersection (video) - Demonstrates DCFL not closed under union (used in many TOC courses). ↩

Closure-property logic for DPDA/DCFL

Identify the class

Step 1

Languages accepted by DPDA are DCFLs."

Footnotes

  1. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

Apply complementation

Step 2

DCFLs are closed under complement."

Footnotes

  1. Deterministic pushdown automaton - Wikipedia - Notes closure: (effectively) closed under complementation but not under union. ↩

Apply union

Step 3

DCFLs are not closed under union."

Footnotes

  1. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

Select MCQ option

Step 4

Only option (i) remains valid."

Deciding the MCQ using closure facts

  1. 1
    Step 1

    Use that languages accepted by deterministic pushdown automata are exactly deterministic context-free languages (DCFLs).

    Footnotes

    1. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

  2. 2
    Step 2

    Use that DCFLs are closed under complement.

    Footnotes

    1. Deterministic pushdown automaton - Wikipedia - Notes closure: (effectively) closed under complementation but not under union. ↩

  3. 3
    Step 3

    Use that DCFLs are not closed under union.

    Footnotes

    1. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

  4. 4
    Step 4

    Since union is not preserved, (iii) and (iv) are false.

  5. 5
    Step 5

    Therefore the correct choice is (i) Complement.

Which operations keep DCFLs within the same class?

Closure for languages accepted by deterministic pushdown automata (DPDA/DCFL).

Pro Tip: Use the right class

First replace “DPDA language” with “DCFL.” Then apply DCFL closure facts: complement yes, union no.2

Footnotes

  1. Deterministic pushdown automaton - Wikipedia - Notes closure: (effectively) closed under complementation but not under union. ↩

  2. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

Common misconception

CFLs are closed under union, but DCFLs are a strict subclass with different closure properties—so you cannot transfer CFL closure results to DPDA languages.

Footnotes

  1. Deterministic context-free language - Wikipedia - Lists closure under complement and explicitly states not closed under union (and intersection). ↩

Exam-ready clarifications

Knowledge Check

Question 1 of 3
Q1Single choice

A language accepted by deterministic pushdown automata is closed under which operation?

Explore Related Topics

1

Pushdown Automata (PDA): Short Note + Core Formalism

2

Ambiguous Grammars in Formal Language Theory: Choosing the Correct Option

3

Epsilon ($\varepsilon$) Transitions in DFA and NFA

Browse all research articles