GATE CS 2002 Q1.7 — Regular and Context-free Languages

A standard Pushdown Automaton (PDA) has a finite state control and an auxiliary stack of infinite capacity. However, if the stack size is restricted to a maximum of $10$ items, the stack can only hold a finite number of configurations.

Let $\Gamma$ be the stack alphabet. The total number of possible stack configurations is given by:

Since $|\Gamma|$ is finite, $N$ is also a finite constant.

We can construct an equivalent Finite Automaton (FA) where each state is a tuple $(q, w)$ representing:

• $q \in Q$: the current state of the PDA's finite control.
• $w \in \Gamma^* \text{ with } |w| \le 10$: the current contents of the stack.

Since the state space of this equivalent automaton is finite ($|Q| \times N$), the machine is a Finite Automaton. Therefore, the language accepted by this restricted PDA is regular.