1

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?

Andrés E. Caicedo
  • 79,201
Maroun
  • 113
  • It would be helpful to know what your exact definition of complementary definition is. – Dominik Jun 23 '13 at 12:31
  • I don't know the formal definition, but as I can guess it would be: Lc = {a,b}*\L. – Maroun Jun 23 '13 at 12:36
  • Is # a new symbol or does it just indicate concatenation? – Dominik Jun 23 '13 at 12:39
  • The words that the DFA will accept are of the form w#w where |w| = k (and # is an actual symbol). – Maroun Jun 23 '13 at 12:41
  • 1
    This is a frequent source of confusion. If $L\subseteq A^$ for a finite set of symbols $A$, then the complement* language $L^c$ is defined to be $A^\setminus L$. However, it might be the case that the question meant by the complementary* language all words of the form $x#y$ that are not of the form $x#x$, in which Dominik's answer is correct. – Rick Decker Jun 23 '13 at 19:51

1 Answers1

1

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\}$$ .

Dominik
  • 14,396