L1={$w^* $| w=x and $ x \in \Sigma^*$}
L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$}
L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x}
a) there is a PDA(push down automata) that accept L2 intersection L3
b) there is a PDA(push down automata) that accept L2 union L3
c) there is a PDA(push down automata) that accept L1 intersection L3
d) there is a PDA(push down automata) that accept L1 union L3
I think (a) is false. can I say 3 and 4 is wrong because we have no language that not closed under union but closed under intersection?
anyone can help me with some detail about the answer of this question?
First notice that $L_1$ is really simple:
$$L_1=\{w^* \mid w=x\text{ and }x \in \Sigma^*\}\supseteq\{w^1 \mid w=x\text{ and }x \in \Sigma^*\} =\Sigma^*$$ Hence $L_1=\Sigma^*$.
Then notice that$L_3$ is also really simple:
$$L_3=\{w \mid w=x.y, x,y \in \Sigma^*, y\text{ is a sub-string of }x\}$$
If as sub-string you allows $\epsilon$, then you van decompose any word $w$ as $w.\epsilon$ hence $L_3=\Sigma^*$.
Otherwise notice that if $y=y_1\dots y_n$ is a sub-string of $x$ then $y_n$ is a sub-string of $x$ hence also of $x.y_1\dots y_{n-1}$. Hence you only have to check that the last letter appear at least once other time in the word. Hence $L_3$ is regular.
Since $L_1$ and $L_3$ are regulars I let you find the answers for c) and d).
For a) and b) notice that $L_2\subseteq L_3$. Then you have to know whether $L_2$ is context free or not ...
For b) L2 is included in L3 so what is the result of the union?.
For c) and d) what do you know about union and intersection of regular language? (if nothing L1=Σ∗ so the union and intersection are pretty simple)