Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$.

It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that $A$ is recognized by finite state automata, while $B$ is recognized by pushdown automata.

But, isn't $B$ a subset of $A$? For example, $01, 0011,000111,\ldots$ are all elements of $A$. My question is that how a language recognized by pushdown automata, not by finite state automata, can be a subset of regular language?

  • 3
    $\begingroup$ Every language is a subset of a regular language: if $\Sigma$ is the alphabet, every language over $\Sigma$ is a subset of $\Sigma^*$. Loosely speaking, the more conditions you impose on the subset, the less likely it is that the language will be regular. $\endgroup$ – Brian M. Scott Jan 30 '16 at 3:57
  • $\begingroup$ Every regular language is a context-free language, but not every context-free language is a regular language. In the above case, A can also be considered as a context-free language, so it may contain another context-free language that is not regular. Is this the correct interpretation of the above problem? $\endgroup$ – Tim Lee Jan 30 '16 at 6:43
  • 1
    $\begingroup$ Not really, no. If a language $B$ is a subset of a language $A$, the classifications of $A$ and $B$ in the Chomsky hierarchy in general have nothing to do with each other. $\endgroup$ – Brian M. Scott Jan 30 '16 at 6:45
  • $\begingroup$ Consider this: Let $P$ be the set of prime numbers other than 2: $\{3,5,7,11,13,17,19,23,\ldots\}$. Let $O$ be the set of odd numbers. It's easy to recognize members of $O$; just look at the last digit. Recognizing members of $P$ is difficult, even though $P$ is a subset of $O$. Or let $X$ be the set of Americans and let $Y$ be the set of Americans who would do a good job if elected President. Members of $X$ are easy to recognize, members of $Y$ much less so. $\endgroup$ – MJD Jan 30 '16 at 14:35

Your Answer

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

Browse other questions tagged or ask your own question.