Intersection of a language with a regular language imply context free

Question

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is context free?

Meaning, given a regular language $P$, if $$L \cap P = T$$ where $T$ is context free, is $L$ is context free?

Let $A =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$ how can I show this is context free? Is the only way to create a PDA or a CFG?

Answer 1

In a nutshell

1. Using closure with one regular language ($\exists P \text{ regular such that }L\cap P$ is context-free) as apparently envisioned in the question does not work. Indeed, for any language $L$ there is a regular language $P$ such that $L\cap P$ is context-free. So there is no way a family of languages can be characterized by this property, other than the family of all languages on an alphabet $\Sigma$, i.e., $2^{\Sigma^*}$.

2. Using a more universal closure property with all regular languages (universal quantification: $\forall P \text{ regular, }L\cap P$ is context-free) does not work either. But, to prove the context-free (CF) property for intersection with any regular set, you have to prove it in particular for the regular set $\Sigma^*$. But $L\cap\Sigma^*=L$, so that you are back to the initial problem of proving that $L$ is CF. This is quite simple, and is not further developed below.

3. The language you are interested in, $A =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$, is indeed context-free. A simple way to establish that is to build a non-deterministic PDA that recognizes it. Intuitively, such a PDA could first work as if recognizing $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$, then switch non-deterministically to the transitions of a PDA recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$ while keeping the same stack.

4. Following site policies, I would also suggest you look at the reference answers to frequently asked questions on this topic, and in particular to How to prove that a language is context-free?.

Using closure as proposed in the question does not work

This is an answer to the first question, since you are actually asking two questions, about using the property of clusre of CF languages with regular sets. You are actually using the property backward, which is not permissible.

There is a very simple counter-example. If you take any language $L$, and any finite subset $R\subset L$, the language $R$ is regular, since all finite languages are regular, and is also context-free since all regular languages are context-free. But $R\subset L$ implies $R\cap L=R$. There is always such a subset $R$ since the empty language $\emptyset$ is regular and is a subset of any other language.

Hence for any language $L$ there is a regular language $P$ and a CF language $T$ such that $L\cap P=T$. You only lave to take $P=T=R$ for some finite subset $R\subset L$ (including the empty one).

Note that this still works when $L=\emptyset$.

The property you are trying to use is a trivial property, in the sense that is is true of any language, without exception. Hence, you cannot infer from it alone any specific property that is not equally trivial.

I use finite subsets because they always exists, while some languages do not have infinite regular subset. Infinite regular subsets work too, when they exist.

Proving that your language $A$ is Context-free

$A =\{x \in \{a,b\}^{\ast} \mid |x|_a < |x|_b < 2|x|_a\}$

There are various ways a language can be proved to be CF. It is always possible to do it with closure properties, because of the Chomsky-Schutzenberger representation theorem ... but that does not mean it is easy.

My suggestion is to build a PDA, actually a non-deterministic one. I have not proved it (so take this with care), but I suspect it cannot be recognized by a deterministic PDA.

If you had to have as many $a$ and $b$, you would use the stack to count the extra $a$'s or the extra $b$, so that you can match the numbers. If you wanted twice as many $b$'s, you would count 2 $b$'s for one $a$, which you can achieve by pushing two $a$'s on the stack for each extra $a$, and matching each with a later $b$, or by matching the $a$ just read with two $b$'s from the stack (I am skipping details). Since you want something in between, you can arbitrarily decide for each $a$ whether it matches one $b$ or two $b$'s.

There is however a much simpler solution (at least simpler to explain) which I give in the next section. But I decided to leave this one as it may be instructive too. So you may choose to skip to the next section.

You also have to be careful that at least one $a$ matches two $b$'s, so that you have strictly more $b$'s than $a$'s, and that at least one $a$ matches a single $b$ so that the number of $b$'s is strictly less than twice the number of $a$'s.

The stack bottom is supposed to be $\$$. The behavior is the same for all states, which are used only to remember an $a$ has matched one $b$, and whether another $a$ has matched two $b$'s.

So you have 4 states: initial $q_0$, then $q_1$ when an $a$ has matched a single $b$, $q_2$ when an $a$ has matched two $b$'s, and $q_b$ when both have occured, which is a requirement to accept thhe string.

When reading an $a$, you decide non-deterministically whether it must match one $b$ or two $b$'s, and possibly change the state acordingly.

• If you decide for a single $b$:

  • If the top of stack is $b$, you just pop that $b$

  • otherwise you push the $a$ on the stack to be matched with a later $b$.

• If you decide for two $b$'s:

  • If the top of stack is $bb$, you just pop these two $b$ (this can be decomposed into two pops, if your PDA model requires it, by introducing other states)

  • if the top of stack is $b$ with no other $b$ in second position, you pop that $b$ and push an $a$.

  • if the top of the stack is not a $b$, you just push 2 $a$'s.

When reading a $b$, you just try to match it on the stack:

• if the top of the stack is an $a$, just pop it.

• otherwise push a $b$ on the stack.

If you reach the end of the input with an empty stack and state $q_b$, then you accept.

Alternative simpler solution

Actually, you do not need to have a PDA that is non-deterministic on each input $a$, and you can make a single non-deterministic choice.

The idea is that you start the PDA working as if it were recognizing $A_1=\{x \in \{a,b\}^{\ast} \mid |x|_a = |x|_b \}$

Then, after reading at least one $a$, you continue recognition as if you were recognizing $A_2=\{x \in \{a,b\}^{\ast} \mid 2|x|_a = |x|_b \}$ and must scan at least one $a$ in that phase.

Of course, this is a single PDA. and you do not change the stack as you switch the recognition mode.

You accept on empty stack.

Note that this does not imply that the string recognized is the concatenation of a string in $A_1$ and a string in $A_2$. The string could be all $a$'s followed by all $b$'s, or the reverse, as long as the number of $a$'s and $b$'s is right.

Answer 2

No, we can construct (heavy-handedly) a counter example by letting $L = L_{1} \cup L_{2}$ where $L_{1}$ is regular (and hence context free) and $L_{2}$ is not context free.

Let $L_{1} = \{1^{n}\mid n\in\mathbb{N}\} = 1^{\ast}$ and $L_{2} = \{\langle M,x\rangle \mid M\text{ is a Turing Machine that halts on input }x\}$.

Then letting $L = L_{1} \cup L_{2}$, clearly $L$ is undecidable, however $$ L\cap L_{1} = L_{1} $$ Clearly $L_{1}$ is regular, and hence context free, even though $L$ is not.

So this approach can't be used to show that $A$ is context free. If you could find a context free language $B$ and a regular language $C$ such that $B\cap C = A$, that would work, but (at a glance) that seems a difficult approach. In this case it should prove simpler to construct a PDA or CFG for $A$, although it is a little fiddly.

The construction below is incorrect, I'll come back and fix it when I have time, in the meantime, Babou's answer has lots of options for PDAs

Taking the PDA approach, we need to keep track of if we have enough $a$s, with the catch that the $b$s might come first, so we need three stack symbols, $\$$ to mark the bottom of the stack, $\alpha$, which we will use (twice) when we see an $a$, and $\beta$ which we will use when we see a $b$, but don't have an $\alpha$ to take off the stack (so it's like a $-\alpha$ that we have cancel out, in some sense).

So the basic operation is:

• If we see an $a$ and there is not $\beta$ on the stack push two $\alpha$s.
• If we see an $a$ and there is a $\beta$ on the stack, pop the $\beta$.
• If we see a $b$ and there is an $\alpha$ on the stack, pop the $\alpha$.
• If we see a $b$ and there is no $\alpha$ on the stack, push a $\beta$.
• When we run out of input, unwind the stack and check for $\beta$s; if there are, go to a sink state, if we find $\$$ without seeing a $\beta$, accept.

If you think about it, or just play around a little, you'll see that there is actually more structure - we can't have a $\beta$ above an $\alpha$ on the stack, which suggests another approach (but that's an exercise).