GATE CS 2005 Q54 — Regular Expressions and Finite Automata

To determine the correct relationship between the classes of languages, we analyze the expressive power of deterministic and non-deterministic models for both finite automata and pushdown automata:

1. Finite Automata ($D_f$ and $N_f$):

   Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA) are equivalent in terms of their language-recognizing power. Every NFA can be converted into an equivalent DFA using the subset construction method. Both models accept the class of Regular Languages.

   $$D_f = N_f$$

2. Pushdown Automata ($D_p$ and $N_p$):

   Deterministic Pushdown Automata (DPDA) accept the class of Deterministic Context-Free Languages (DCFLs), whereas Non-deterministic Pushdown Automata (NPDA) accept the class of all Context-Free Languages (CFLs).

   Non-determinism strictly increases the power of pushdown automata. For example, the language of even-length palindromes, $L = \{ww^R \mid w \in \{a, b\}^*\}$, is a CFL but not a DCFL. Thus, DCFLs are a strict subset of CFLs.

   $$D_p \subset N_p$$

Combining these two results, we get:

$$D_f = N_f \quad \text{and} \quad D_p \subset N_p$$

Therefore, the correct option is D.