World's most popular travel blog for travel bloggers.

# How do I interpret this formal languages definition?

, ,
Problem Detail:

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?

Example:

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.

Question Source : http://cs.stackexchange.com/questions/64127

3200 people like this