1
$\begingroup$

You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does not belong to a certain class of languages, you might think that it will be more convenient to prove it by using a subset of that language. The problem is that a subset of a language does not necessarily belong to the same language class as the superset language. For example: with $\Sigma = \{0,1\}$, $\Sigma^*$ is a regular language, while $ A = \{ 0^n1^n \mid n \geq 0\} \subseteq \Sigma^* $ is a context free language.

(I have fallen in the trap of trying to use subsets of languages in order to try to prove that they belong to a certain class of languages.)

An example:

Let $\Sigma = \{0,1\} $ and $L = \{ w \in \Sigma^* \mid \text{w contains less 1's than 0's} \}$

Is $L$ regular, context free, or neither?

My intuition says that it is not regular, since finite state machines can't count. I think it is context free.

The strategy I'm thinking of is to show that this language is context free:

$ L_2 = \{ 0^n1^m \mid n \gt m\}$

This language is clearly a proper subset of $L$. But, like we've seen, that may not be a very useful fact if we want to prove things about the proper superset (to my understanding). It seems that $L_2$ is easier to generate than $L$: it seems easier to count how many consecutive 0's there are rather than counting the number of 0's in a string. (Especially if you consider using a PDA to count it, since then it just boils down to pushing consecutive 0's and then popping when you start seeing 1's, accepting the language if there are 0's left on the stack when you have consumed the word.) Consequently, if this intuition of hardness is correct, then $L$ is at least not regular. But then another problem reveals itself; maybe $L$ is not context free? So then you have at least shown it to not be regular, but you still have to show that it is context free or not.

This is not the only problem for which I want to use this strategy. For example:

$L_p = \{ w \in \Sigma^* \mid \text{the number of 0's in w is prime}\}$

Here I think it might be more convenient to use something like the Pumping Lemma on this language:

$L_{p2} = \{ 0^n \mid \text{n is prime}\}$

Is this kind of strategy valid?

$\endgroup$
6
$\begingroup$

Yes. The formal way to name this trick is the use of closure properties. In your specific case the families (regular, context-free) are closed inder intersection with a regular language: if $K$ is regular (context-free) then so is $K\cap R$, where $R$ is regular.

In your examples $L_2 = L \cap 0^*1^*$ and $L_{p2} = L_p \cap 0^*$.

So, if $L_{p2}$ isn't context-free then neither is $L_p$. Also if $L_2$ isn't regular then neither is $L$.

Regarding the first part of you question this will not help: $L_2$ may be context-free while $L$ isn't. (Not is this example, where they both are context-free: use pushing and popping but in a more general way, think how to represent negative numbers.) On the other hand, when you are not able to solve the general case, it might be helpful to develop intuition on the special cases.

$\endgroup$

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.