If you want to make money online : Register now

[Solved]: Language member explanation

, , No Comments
Problem Detail: 

Given the following formal language $L$:

$$ L=\{ww \mid w\in\{a,b\}^*\}$$

Why is $a$ not a member of this language?

So what is $\{a,b\}^*$ exactly? I thought it means $(a+b)^*$?

Asked By : wildplace

Answered By : Yuval Filmus

The notation $\{a,b\}^*$ stands for all strings over the alphabet $\{a,b\}$. A word is in the language $L$ if it is of the form $ww$, where $w$ is an arbitrary word over the alphabet $\{a,b\}$. For example, taking $w = aba$, we see that $abaaba \in L$. If $w$ has length $n$ then $ww$ has length $2n$, and in particular every word in $L$ has even length. So $a \notin L$. But this idea isn't enough to prove that $ab \notin L$.

If $x$ is a word of odd language, then $x \notin L$. If $x$ has length $2n$, then write $x=yz$, where $y$ consists of the first $n$ characters, and $z$ consists of the last $n$ characters. Then $x \in L$ if and only if $y=z$. If $x=ab$ then $y=a$ and $z=b$ and so $y \neq z$, implying $ab \notin L$.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback