Intersections of some context-free languages

Question

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.

Answer 1

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.