[Math] Regular expression of the set of strings of even length

formal-languagesregular expressionsregular-language

I should try to write a regular expression of the set of strings of even length over $\{k,l,m\}$ that contain exactly one $k$. If string has even length, and if we have one $k$; there should be (odd length $l$ and even length $m$) or (even length $m$ and odd length $l$). However, I couldn't show them, especially place of $k$ in the expression.

I hope I could tell my ideas correctly.

Best Answer

I'm not sure what rules are available for your definition of regular expression, but following works in Unix (as an extended regular expression): ([lm][lm])*(k[lm]|[lm]k)([lm][lm])*

Edit: (I also removed the unnecessary anchors that Milo Brandt comments on.)

Breaking this down:

  • [lm] = represents a single character that could be either l or m. In the wikipedia regex page, this would be expressed by (l|m).
  • ( ) * | all mean the same as explained in the Basic Concepts section of the Wikipedia Regular Expressions page.
  • ([lm][lm])* is thus a string of any even number of ls and ms.
  • (k[lm]|[lm]k) is either k followed by an l or an m, or it is an l or m followed by a k.

So the whole expressions says "a string starting with any number of any of the substrings ll, lm, ml, mm, followed by one of the substrings kl, km, lk, lm, followed by any number of any of the substrings ll, lm, ml, mm.

Every string from $\{m, l, k\}$ of even length with exactly one $k$ in it will match this.

Related Question