World's most popular travel blog for travel bloggers.

How do I interpret this formal languages definition?

, , No Comments
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?


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

Asked By : netik
Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback