2
$\begingroup$

I'm not exactly sure how to go about this.

Thanks

  • 0
    Is this maybe a StackOverflow question? Please show what you need it for, and what you have tried so far.2012-02-20
  • 0
    No, this wouldn't be a StackOverflow question. I just need to show the expression which expresses the alphabet $(a, b, c)$ using the language I have mentioned above. I'm not sure how to do this, but i have done something like $(a|b|c|aaa|bbb|ccc)$ and so on, including every odd charactered combination.2012-02-20

1 Answers 1

4

Hint:

What language does $(aa)^*$ represent over the alphabet $\{a\}$?

  • 0
    So would it be $a^*|b^*|c^*$?2012-02-20
  • 1
    What you have mentioned represents the language of all words that have even length.2012-02-20
  • 0
    @akshai5050: No, $a*|b*|c*$ is not correct. You can verify it yourself, by trying out some sample strings. Yes to the second comment.2012-02-20
  • 0
    Yes, I now realise what I said wouldn't be correct, as even lettered words would also be accepted by the expression. So, would it then be $a(aa)^*|b(bb)^*|c(cc)^*$?2012-02-20
  • 0
    @akshai5050: What about words like $abc$? You miss those, don't you?2012-02-20
  • 0
    Yes, now given that you can represent all words that have even length, how can you extend that idea to all words of odd length?2012-02-20
  • 0
    @Aryabhata: $a(aa)^∗|b(bb)^∗|c(cc)^∗|abc|cba|acb|bca|bac|cab$ would this be ok?2012-02-20
  • 0
    or could it be changed to: $a(aa)^∗|b(bb)^∗|c(cc)^∗|(a(aa)^*b(bb)^*c(cc)^*)^*$?2012-02-20
  • 0
    @akshai5050: Trying solving the problem when the alphabet is $\{a,b\}$. Try and see if you can do words which mix $a$ and $b$.2012-02-20
  • 0
    From what I understand, that would not be possible, because of the $c$ before $(cc)^*$. I am not sure how to go about solving this though.2012-02-20
  • 0
    @akshai5050: Is there a regular expression for the language where the string is either $a$ or $b$?2012-02-20
  • 0
    Yes, this part: $a(aa)^∗|b(bb)^∗$2012-02-20
  • 0
    @Aryabhata $$a(aa)^∗|b(bb)^∗|c(cc)^∗|(a(aa)^∗b(bb)^∗c(cc)^*)^*|(a(aa)^*b(bb)^*)^*|(b(bb)^*c(cc)^*)^*|(a(aa)^*c(cc)^*)^*$$ I think this is right.2012-02-20
  • 0
    @akshai5050: No. For the two letter case, you miss words like $abababb$. It is not just $aaaaa$ or $bbbbb$. Ok, here is a question, how would you represent the set of _all_ possible strings using the alphabet $\{a,b\}$?2012-02-20
  • 0
    @Aryabhata $(a|b|c)((a|b|c)(a|b|c))^*$2012-02-20
  • 0
    @Aryabhata The answer to your question would be: $(a^*b^*)^*$2012-02-20
  • 0
    @akshai5050: Well done, seems like you got it. In the last one, why not just write (a|b)*?2012-02-20
  • 0
    @Aryabhata Yes, you're right. Thanks a lot for the help. Much appreciated.2012-02-20