GATE CS 1998 Q1.10 — Regular Expressions and Finite Automata

A language can be recognized by a Deterministic Finite Automaton (DFA) if and only if it is a regular language. Let us analyze each option:

• Option A: The numbers $1, 2, 4, 8, \dots, 2^n, \dots$ written in binary.
  In binary, these numbers are represented as:
  $$\begin{align*}1 &= 1_2 \\ 2 &= 10_2 \\ 4 &= 100_2 \\ 8 &= 1000_2 \\ &\vdots \\ 2^n &= 10^n_2\end{align*}$$The set of these binary strings is represented by the regular expression $10^*$. Since it can be described by a regular expression, the language is regular and can be recognized by a DFA.
• Option B: The numbers $1, 2, 4, 8, \dots, 2^n, \dots$ written in unary.
  In unary, a number $k$ is represented by a sequence of $k$ identical symbols (say, $1$). The set of strings is:
  $$L = \{1^{2^n} \mid n \ge 0\} = \{1, 11, 1111, 11111111, \dots\}$$Since the gap between consecutive string lengths grows exponentially, this language violates the pumping lemma for regular languages. Hence, it is not regular.
• Option C: The set of binary strings with an equal number of zeros and ones.
  This language is $L = \{w \in \{0,1\}^* \mid N_0(w) = N_1(w)\}$. Recognizing this language requires counting and comparing the occurrences of $0$s and $1$s, which requires infinite memory. Hence, it is a deterministic context-free language (DCFL) but not regular.
• Option D: The set $\{1, 101, 11011, 1110111, \dots\}$.
  This set can be written as $L = \{1^n 0 1^n \mid n \ge 0\}$ (where $n=0$ gives $1$, $n=1$ gives $101$, etc.). This requires matching the number of $1$s before and after the $0$, which cannot be done with finite states. Thus, it is not regular.

Therefore, only the set in Option A can be recognized by a DFA.