0
$\begingroup$

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.

  • 1
    @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".2012-02-21

1 Answers 1

2

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.