[Math] Determine string is even length with regular expression

formal-languagesregular expressions

There is a set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. And I try to write its regular expression.

I think it can be in that format:

   ODD PREFIX k EVEN SUFFIX | EVEN PREFIX k ODD SUFFIX

Is this idea true? If it is true, it looks too long, is there any shorter way to write it?

Best Answer

Although your answer shows that you have understood the question, you need to be more precise. In particular, the prefix and the suffix should be words on the alphabet $A = \{l, m\}$. Then, step by step, one has:

  1. The set of words of even length on the alphabet $A$ is $(AA)^*$.
  2. The set of words of odd length on the alphabet $A$ is $(AA)^*A$.
  3. According to your idea, which is right, your language is $(AA)^*k(AA)^*A \cup (AA)^*Ak(AA)^*$.
Related Question