Finding the complementary language of a given language

45 Views Asked by At

I'm trying to figure out what's the complementary language of:

L = {w#w : w∈{a,b}*, |w| = k}

I think it's the language of all the words w#w where |w|!=k.

I think my answer is not correct. How should I think about this? And what is the correct answer?

1

There are 1 best solutions below

4
On BEST ANSWER

Hint: Since L contains only words like $abb#abb$ with the property that they repeat themselves (with a "#" in the middle), words like $abb#bab$ where the second part is different from the first part will not be in your language.

Now it is easy to see that $$L^c=\{a\text{#}b|a\ne b, |a|=|b|=k\}$$ .