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\}$?
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