# Regular Expressions - Over the alphabet $(a, b, c)$

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.

-
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 cstheory.stackexchange.com 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