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.
Intersections of some context-free languages
formal languages;context free;automata;pushdown automata
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:$L_2 \cap L_3 = L_2 \cap \Sigma^* = L_2$$L_2 \cup L_3 = L_2 \cup \Sigma^* = \Sigma^*$$L_1 \cap L_3 = \Sigma^* \cap \Sigma^* = \Sigma^*$$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$:$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.$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.$vxy$ consists of a $1$s from the first (parenthesized) part only. See argument in point 1 above.$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.