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
    $\begingroup$ (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. $\endgroup$ – FrankW Oct 17 '14 at 8:42
  • $\begingroup$ Dear @FrankW, (1) yess. (2) i didnt any idea, i think L1 and L3 is regular. $\endgroup$ – T. Jzmod Oct 17 '14 at 8:54
  • $\begingroup$ $\{w^* | w=x \text{ and } x \in \Sigma^*\} = \{w^* | w\in \Sigma^*\}$ $\endgroup$ – babou Oct 17 '14 at 10:30
  • $\begingroup$ Dear @babou, Yes $\endgroup$ – T. Jzmod Oct 17 '14 at 10:34
  • 1
    $\begingroup$ @FrankW It may be that the instructor gave convoluted definitions to force students to first simplify them. $\endgroup$ – babou Oct 17 '14 at 10:41

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.

  • $\begingroup$ would you please say regular language closed under union and intersection? $\endgroup$ – T. Jzmod Oct 17 '14 at 15:38
  • $\begingroup$ @T.Jzmod Regular languages are closed under both union and intersection. $\endgroup$ – Patrick87 Oct 17 '14 at 15:46
  • $\begingroup$ so there is no PDA for L2? am i right? thanks so much. $\endgroup$ – T. Jzmod Oct 17 '14 at 16:19
  • $\begingroup$ @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. $\endgroup$ – Patrick87 Oct 17 '14 at 16:27
  • $\begingroup$ If it's any help, I agree that your proof sketch is indeed correct. It's an ugly, but straightforward exercise. $\endgroup$ – Rick Decker Oct 18 '14 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.