0
$\begingroup$

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.

$\endgroup$
5
  • 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, 2014 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, 2014 at 8:54
  • $\begingroup$ $\{w^* | w=x \text{ and } x \in \Sigma^*\} = \{w^* | w\in \Sigma^*\}$ $\endgroup$
    – babou
    Oct 17, 2014 at 10:30
  • $\begingroup$ Dear @babou, Yes $\endgroup$
    – T. Jzmod
    Oct 17, 2014 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, 2014 at 10:41

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ would you please say regular language closed under union and intersection? $\endgroup$
    – T. Jzmod
    Oct 17, 2014 at 15:38
  • $\begingroup$ @T.Jzmod Regular languages are closed under both union and intersection. $\endgroup$
    – Patrick87
    Oct 17, 2014 at 15:46
  • $\begingroup$ so there is no PDA for L2? am i right? thanks so much. $\endgroup$
    – T. Jzmod
    Oct 17, 2014 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, 2014 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$ Oct 18, 2014 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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