# Intersections of some context-free languages

Suppose We have Some language as follows:

$L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$

$L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$

$L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a substring of } x\}$

1) there is a PDA (push down automata) that accept $L_2 \cap L_3$

2) there is a PDA (push down automata) that accept $L_2 \cup L_3$

3) there is a PDA (push down automata) that accept $L_1 \cap L_3$

4) there is a PDA (push down automata) that accept $L_1 \cup L_2$

I read in some sites that:

(a) is false, and we can say 3 and 4 are wrong because we have no language that is not closed under union but closed under intersection.

I read a lot of material for finding the answer of this question mentioned by Prof. M. Farshchi on Entrance Exam in 2012, but I failed. I need some one to help me with a bit detail for each one. Thanks.

• (1) Is "$w=x$ and $x\in \Sigma^*$" just a convoluted way of saying $w\in\Sigma^*$, or do you want to express something else? (2) What do you mean by $\Sigma + \Sigma$? (3) Languages are never closed under union and intersection, that is a property of language classes. Also it does not help here, since $L_1$ and $L_2$ are not context-free. – FrankW Oct 17 '14 at 8:42
• Dear @FrankW, (1) yess. (2) i didnt any idea, i think L1 and L3 is regular. – T. Jzmod Oct 17 '14 at 8:54
• $\{w^* | w=x \text{ and } x \in \Sigma^*\} = \{w^* | w\in \Sigma^*\}$ – babou Oct 17 '14 at 10:30
• Dear @babou, Yes – T. Jzmod Oct 17 '14 at 10:34
• @FrankW It may be that the instructor gave convoluted definitions to force students to first simplify them. – babou Oct 17 '14 at 10:41

## 1 Answer

Notice that $L_3 = \Sigma^*$, since you can always choose $y=\epsilon$ (the empty string is a substring of any string) and then choose $x$ from $\Sigma^*$. $L_1$ is also $\Sigma^*$, since $L$ is always a subset of $L^*$ and we're basically saying $L_1 = (\Sigma^*)^*$. These observations imply the following: the answers to #2, #3 and #4 are "yes" (indeed, there's a DFA with one state accepting each of these, which are all $\Sigma^*$)... and the intersection in #1 is simply $L_2$, so the question is really "is $L_2$ context-free?"

Please also note that we have other questions on the site about proving and disproving that languages are context-free.

To clarify:

1. $L_2 \cap L_3 = L_2 \cap \Sigma^* = L_2$
2. $L_2 \cup L_3 = L_2 \cup \Sigma^* = \Sigma^*$
3. $L_1 \cap L_3 = \Sigma^* \cap \Sigma^* = \Sigma^*$
4. $L_1 \cup L_2 = \Sigma^* \cup L_2 = \Sigma^*$

As for $L_2$:

First note that I'm assuming $(\Sigma + \Sigma)^*$ is a funny way of writing $\Sigma^*$. Plus usually stands in for union when dealing with regular expressions, and I'm guessing that's the intention here as well, though it would be well to confirm this.

Assume $L_2$ were context free. By the pumping lemma for context-free languages, we could write any word $w \in L_2$ of length at least $p$ as $uvxyz$ where $|vxy| \leq p$, $|vy| > 0$ such that $uv^kxy^kz \in L$ for all $k \geq 0$. Consider the word $(0^p1^p)(1^p0^p)(0^p1^p)(1^p0^p)\in L_2$ (parentheses added for clarity). We consider cases for the assignment of $vxy$:

1. $vxy$ consists entirely of $0$s from the first (parenthesized) part of the string. Pumping will change the number of $0$s without changing the number of $1$s in the first part, leading to a string that can't possibly be in the language.
2. $vxy$ consists of a mix of $0$s and $1$s from the first (parenthesized) part of the string. Pumping will change the numbers of $0$s and $1$s in the first part without affecting the other parts, leading to a string that cannot be in the language.
3. $vxy$ consists of a $1$s from the first (parenthesized) part only. See argument in point 1 above.
4. $vxy$ consists of $1$s from the first part and $0$s from the second. See arguments above.

etc. There are 15 cases in total, but the arguments are all basically the same: you always get some parts out of sync (the $p$s won't match). This means that the language is not context-free.

• would you please say regular language closed under union and intersection? – T. Jzmod Oct 17 '14 at 15:38
• @T.Jzmod Regular languages are closed under both union and intersection. – Patrick87 Oct 17 '14 at 15:46
• so there is no PDA for L2? am i right? thanks so much. – T. Jzmod Oct 17 '14 at 16:19
• @T.Jzmod It's not a context-free language (unless my proof sketch and intuition are incorrect), so no, there is no PDA for it. – Patrick87 Oct 17 '14 at 16:27
• If it's any help, I agree that your proof sketch is indeed correct. It's an ugly, but straightforward exercise. – Rick Decker Oct 18 '14 at 2:32