Take the 2-minute tour ×
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.

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|improve this question
    
@Gerry Sorry, didn't mean to be rude. I have edited the question to show what I have done so far, but I am not sure if it is right. I have also added the homework tag. Thanks. –  AkshaiShah Feb 20 '12 at 23:05
1  
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
2  
@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
1  
Just a quick note: are you aware of cstheory.stackexchange.com dedicated to CS? –  nodakai Feb 20 '12 at 23:55
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". –  David Lewis Feb 21 '12 at 1:36

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.