# $a_k$ is $\{L :\exists M$ a pushdown automaton with bounded stack of size $k$ which accept $L\}$ what is the set $\bigcup_1^\infty a_k$?

A related question: How to prove that a bounded pushdown automaton is regular?

Well I proved that $$a_k$$ for each $$k$$ is the set of all the regular language. Thus $$\bigcup_1 ^{\infty} a_k = \bigcup_1 ^{\infty}\{$$ the set of all regular languages} = $$\{$$ The set of all regular languages $$\}$$.

However before noticing that $$a=\bigcup_1^\infty a_k$$ is taking unions of the same set, I thought that the Context-Free-Languages might be a subset of $$\bigcup_1^\infty a_k$$. So, I wish for someone to point out the flaw of the next explanation:

Let $$L$$ a CFL, and $$M$$ a pushdown automaton which accepts $$L$$. Now denoting $$L_k = \{w\in L : M$$'s stack size $$\le k$$ throughout $$w$$'s reading process $$\}$$ each $$L_k$$ is a regular language because $$L_k \in a_k$$. (I think that was the shaky point, but I can't explain why this claim is wrong). So $$L = \bigcup_1^\infty L_k \in\bigcup_1^k a_k =a$$.

The flaw is in the claim $$\bigcup_{k=1}^\infty L_k \in\bigcup_{k=1}^\infty a_k$$. That is not a valid conclusion. It doesn't follow from the fact that $$L_k \in a_k$$ for each $$k$$.
(Consider: just because $$3 \in S_1$$ and $$5 \in S_1$$, it doesn't follow that $$3+5 \in S_1 \cup S_2$$. Just because $$L_1 \in S_1$$ and $$L_2 \in S_2$$, it doesn't follow that $$L_1 \cup L_2 \in S_1 \cup S_2$$. Just because $$L_k \in a_k$$ for each $$k$$, it doesn't follow that $$\bigcup L_k \in \bigcup a_k$$. In fact, it is correct that $$L_k \in \bigcup a_k$$ holds for each $$k$$, but $$\bigcup L_k \in \bigcup a_k$$ doesn't hold; the regular languages are not closed under infinite unions.)
For instance, pick $$L= \{0^n 1^n : n \in \mathbb{N}\}$$; this is perhaps the canonical CFL that isn't regular. Work through what your proof claims about that $$L$$, and check each statement to see if it is valid. Well, $$L_k = \{0^n 1^n : n \le k\}$$, and sure enough, it is correct that $$L_k \in a_k$$ for each $$k$$. It is also correct that $$L = \cup_{k=1}^\infty L_k$$. However, when you check the claim that $$\bigcup_{k=1}^\infty L_k \in\bigcup_{k=1}^k a_k$$, you discover that the claim is not correct, as the left-hand side is $$L$$ and the right-hand side is the set of all regular languages and $$L$$ is not regular. So, that's the step you should be suspicious of.