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.

  • 0
    I think your current expression accepts `aabb`. You're very close, though.2012-02-20
  • 0
    @Peter Should I put brackets around each 'or' section?2012-02-20
  • 0
    @Peter $((a(a|b|c)^*a)|(b(a|b|c)^*b)|(c(a|b|c)^*c))^*|\epsilon$ Would this be right?2012-02-20
  • 0
    The only problem I see with that is that you don't accept the strings $a$, $b$, or $c$ (single-character strings) which by your explanation, should be accepted.2012-02-20
  • 0
    @Kurtis $((a(a|b|c)^*a)|(b(a|b|c)^*b)|(c(a|b|c)^*c))^*|\epsilon|(a|b|c)^* $ Would this be correct then?2012-02-20
  • 0
    @Kurtis Actually, would this be a simpler solution? $(a(a|b|c)^*a^*|b(a|b|c)^*b^*|c(a|b|c)^*c^*)^*|\epsilon$2012-02-20
  • 0
    No. First off, the last bit - $(a|b|c)^*$ - allows any characters to be chosen any number of times. That is simply the infinite language over all characters in the alphabet. Also, wrapping a $*$ operator around the larger expression just says "we can have any of these any number of times," which means you can have a string beginning and ending with $a$ concatenated with a string beginning and ending with $b$, for example, which is not what you want.2012-02-20
  • 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$.2012-02-20
  • 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.2012-02-20
  • 0
    @Kurtis I don't understand how I could represent a single character with your answer.2012-02-20
  • 0
    @Brandon Would this be correct? $(a(a|b|c)^∗a)|(b(a|b|c)^∗b)|(c(a|b|c)^∗c)|ϵ|(a|b|c)$2012-02-20
  • 0
    @akshai5050 Yes.2012-02-20
  • 0
    That is looking pretty good. How would you "test" it?2012-02-20
  • 0
    @David I would use a combination of words which satisfy the language, such as $aaaaa, bacacb, a, bb, cabac$ e.g. I know the characters in the middle will not matter, because of the kleene star after the "or" sections.2012-02-20
  • 1
    Just a quick note: are you aware of http://cstheory.stackexchange.com/ dedicated to CS?2012-02-20
  • 0
    @nodakai Thanks a lot, that looks good.2012-02-21
  • 0
    @akshai5050 I apologize for the confusion. As was said, what you have above is correct.2012-02-21
  • 0
    @nodakai cstheory tends towards research level questions. This site is more appropriate for basic automata questions.2012-02-21
  • 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.