Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Express the language of all words whose first letter, if it exists, is the same as its last letter over the alphabet $(a, b, c)$.

This is what I have so far: $(a(a|b|c)^*a|b(a|b|c)^*b|c(a|b|c)^*c)^*|\epsilon$

I am not sure if this is right.

share|cite|improve this question
I think your current expression accepts aabb. You're very close, though. – Peter Taylor Feb 20 '12 at 23:11
You have the right answer in there. This should work: $a(a|b|c)^*a | b(a|b|c)^*b | c(a|b|c)^*c$. – Kurtis Zimmerman Feb 20 '12 at 23:27
@akshai5050 No, your language now accepts any string over $\{a,b,c\}$. To put this simply, you seem "Kleene star happy". You keep adding them unnecessarily, and it is allowing extra strings into the language. Hint: $((a(a|b|c)^∗a)|(b(a|b|c)^∗b)|(c(a|b|c)^∗c))^∗|ϵ|(a|b|c)^∗$ is almost correct, just take out a few of the Kleene stars. – Brandon Carter Feb 20 '12 at 23:28
Just a quick note: are you aware of dedicated to CS? – nodakai Feb 20 '12 at 23:55
@ahshai5050 -- right up to a point. You should devise a set of "test cases" just the same you would for software. It's an infinite set, of course, but strive for a representative subset, with corner and special cases represented. You have a good start on that. Then for each, write it under the regular expression and match up the parts from left to right, to "run the test". Do this mechanically -- don't try to "reason" once you have the test cases -- match them algorithmically, as a computer would, until you are "convinced" that the regular expression "works". – David Lewis Feb 21 '12 at 1:36
up vote 2 down vote accepted

Hint -- Start over, but take it step by step. Here's a suggested sequence. How would you express the language of words that begin and end with "a" and have nothing but c's in between, in fact, zero or more c's. If you get that, generalize to starting and ending with "a" or starting and ending with "b". Then generalize the stuff in between, the arbitrary number of c's, to satisfy the original problem. At that point, you will be almost home and can probably figure out the final steps for yourself.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.