3
$\begingroup$

This is the homework question:

$ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $

This is my answer:

$$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | (bca)^* | (ba)^* | (bc)^*)^* | ((cab)^* | (cba)^* | (ca)^* | (cb)^*)^* | ((\epsilon +a) | (\epsilon + b) | (\epsilon+c)) \} $$

Is there a way to simplify this expression?

Improve this question
$\endgroup$
8
  • $\begingroup$ How did you get the expression? $\endgroup$
    – mrk
    Commented Feb 4, 2013 at 22:03
  • $\begingroup$ My head. It could be wrong... $\endgroup$
    – jsan
    Commented Feb 4, 2013 at 22:07
  • 1
    $\begingroup$ I mean, what line of reasoning did you follow? That could help simplify the expression. $\endgroup$
    – mrk
    Commented Feb 4, 2013 at 22:08
  • 1
    $\begingroup$ Well basically it's split in 4 parts. Each part assures that the last letter of each iteration cannot be the the same as the first, so that there could never be an 'aa', 'bb', 'cc'. The last part is a string of length 1 (either a, b, or c). Hope this clarifies, and thanks. $\endgroup$
    – jsan
    Commented Feb 4, 2013 at 22:14
  • 2
    $\begingroup$ I agree with the above comments: It isn't enough if the result is "right", you must be able to convince your TA (and yourself too) that it is right. The reasoning behind the construction is an integral part of your solution. $\endgroup$
    – vonbrand
    Commented Feb 4, 2013 at 23:10

1 Answer 1

Reset to default
4
$\begingroup$

Let's solve this exercise "by induction". Suppose first that the alphabet is only $a,b$. In this case, the only possible words are $ababab\ldots$ and $bababa\ldots$, and you can write a simple regular expressions for them. Now take such a word over the alphabet $a,b,c$. You can break it apart as $w_1 c w_2 c w_3 c \ldots$, in which $w_i \in \{a,b\}^*$. We already have a regular expression describing the $w_i$, so we can write one for the language in question. This approach is general, and you can apply it to any alphabet size.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If the $w_i's$ are allowed to be $\epsilon$, you will get successive $c's$. If not, you can't start your regex with $c$ because it starts with $w_1$ which, in turn, starts with $a$ or $b$! $\endgroup$
    – mrk
    Commented Feb 4, 2013 at 23:01
  • $\begingroup$ Oh, just allow $c w_1 c w_2 c \ldots$ to start (and for symmetry to end in a $w_n$ or $c$) $\endgroup$
    – vonbrand
    Commented Feb 4, 2013 at 23:07
  • $\begingroup$ And BTW, consider that the $a b$ words can end in $a$ or $b$ (they could be even or odd length). $\endgroup$
    – vonbrand
    Commented Feb 4, 2013 at 23:11
  • 1
    $\begingroup$ @saadtaame You're right, a few details are missing. After all, it's not me who has to write the solution to the exercise. $\endgroup$
    – Yuval Filmus
    Commented Feb 5, 2013 at 0:13
  • $\begingroup$ @YuvalFilmus Right. $\endgroup$
    – mrk
    Commented Feb 5, 2013 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.