Given the formal language

$L_1 = \{wcw | w\in \{a,b\}^+\} $

Does this definition requires $w$ to be exactly the same before and after the terminal character $c$ or can it be different?


Are $aabca$ or $abca$ accepted words of $L_1$, or only words like $aabcaab$ or $aca$?


It's the same $w$. You can think of this language in a ``procedural'' way: it is formed by taking every word $w\in \{a,b\}^+$, and for each such word, adding to the language the word $wcw$.

Typically, sets (and languages in particular) are described as $\{x: \text{condition on } x\}$, which is pretty clear. However, it is sometimes more convenient to ``push'' the condition into the description of an element.

That is, you could describe the same language as: $$\{x\in \Sigma^*:\ \exists w\in \{a,b\}^+\wedge x=wcw\}$$ Or even worse: $$\{\sigma_1\cdots \sigma_n: \exists k\ge 1,\ n=2k+1\wedge \sigma_1\cdots\sigma_k=\sigma_{k+2}\cdots\sigma_{2k+1}\wedge \sigma_{k+1}=c\wedge \forall 1\le i\le k,\ \sigma_i\in \{a,b\}\}$$

But obviously this is much more cumbersome than the original description.

  • $\begingroup$ @HendrikJan Right. Added this before the explicit one. $\endgroup$ – Shaull Oct 2 '16 at 12:08

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.