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$.


1 Answer 1


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.)

You won't always have us to check every dubious proof, so let me teach you two techniques you can use if you run across a proof that you are suspicious/skeptical of:

  1. If you're not sure whether to be convinced of a proof, try taking each individual step and writing out a detailed proof of it. If you started with a 4-line proof sketch, this might turn into a 40-line proof, so it's tedious, but it's often a good way to discover whether the proof is valid (sometimes when it comes time to write down the justification, you discover that that step that looks obvious in writing isn't actually so obvious).

  2. Pick a specific example and work through what the logic of the proof is saying about that example. Check whether the logic is valid for that particular example.

    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.