2
$\begingroup$

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$$(a+b)^∗$. But my question is why they taking always $w$ as $\epsilon$ to prove it is regular. In that same logic why $ww$ isn't regular by taking $w$ as $\epsilon$?

$\endgroup$
3
  • $\begingroup$ Because if you take $w$ as $\epsilon$ you can produce any string. Nothing is added to the set with other values of $w$, because they are already present. Please remember that a string is just a string. It does not magically retain the mechanism by which it was produced. $\endgroup$
    – rici
    Aug 10, 2021 at 3:20
  • $\begingroup$ @rici If I take $x =a$ and $w=a^nb^n$, then how can you say it is regular for first language? $\endgroup$
    – Punia
    Aug 10, 2021 at 3:47
  • $\begingroup$ That subset is not regular but that doesn't matter. The question is whether the language as a whole is regular. And it is, because any string composed of $a$ and $b$ is in the language. $\endgroup$
    – rici
    Aug 10, 2021 at 5:06

2 Answers 2

5
$\begingroup$

If you take $w=\varepsilon$ in the second language, you can only create the word $ww = \varepsilon \varepsilon = \varepsilon$. This is not the case in the first language because of the $x$ factor that gives you all the freedom of choice you need.

$\endgroup$
15
  • $\begingroup$ If I take $x$ $= a$ and $w= a^nb^n$, then how can you say it is regular for first language? $\endgroup$
    – Punia
    Aug 10, 2021 at 2:58
  • $\begingroup$ @Saslok The word you describe is $aa^nb^n$ which is clearly in the language for $x = aa^nb^n$ and $w = \epsilon$. A language is a set. $\{xww|x,w∈(a+b)^*\}$ is only one possible description of that set, but that description is not the language itself. You cannot impose arbitrary additional requirements (which is what you are doing), you can only check whether a word is in the set or not. And all words over $\{a,b\}$ are in this set. $\endgroup$
    – idmean
    Aug 10, 2021 at 5:58
  • $\begingroup$ @idmean please elaborate with example "A language is a set. ${xww|x,w∈(a+b)^∗}$ is only one possible description of that set, but that description is not the language itself". $\endgroup$
    – Punia
    Aug 10, 2021 at 6:07
  • $\begingroup$ @Saslok Well, you can just change variable names for a start $\{yuu|y,u∈(a+b)^*\}$. Or, since we have already established that the language is equivalent to $\{a,b\}*$, you could just write that. Or you could come up with something more convoluted like $\{yu|y \in (a+b)^*, u \in \{\epsilon, aab, baa\} *\}$. The point here is that it doesn't matter which values can occur after the prefix $y$ (which can be any word over $\{a,b\}$) as long as the suffix $u$ (or $ww$ in the original description) can be empty. Then, clearly, your language is equivalent to $\{a,b\}^*$. $\endgroup$
    – idmean
    Aug 10, 2021 at 6:13
  • $\begingroup$ @idmean thank you.. But I want to understand what is description and language? $x=aa^nb^n$ is one possible description of the language {${xww|x,w∈(a+b)^∗} $} ? $\endgroup$
    – Punia
    Aug 10, 2021 at 6:56
1
$\begingroup$

We know that , any language is a subset of $\Sigma^*$. Hence union $\Sigma^*$ with any other languages is $\Sigma^*$. Note that $x$ is $\Sigma^*$, and one of the strings that can be obtained from $ww$ is $\epsilon$, so concatenation $x$ with $ww$ can be as bellow:

$$\Sigma^*\cup \dots=\Sigma^*.$$

So actually $L$ is $\Sigma^*$ that already we know it's regular, because there is DFA for it.

$\endgroup$
0

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.