Challenge on Some Language and PDA

205 Views Asked by At

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

There are 1 best solutions below

0
On BEST ANSWER
  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^*$