1
$\begingroup$

I have the following question regarding a situation given and we are then required to derive a regular expression out of it.

enter image description here

What i have to do now i to give a regular expression for this language described by the knob movement from A,B and C. Because i have to go through B if i were to traverse to C, and vice versa, i know that B must be present as part of the expression.

Here's what i attempted:

ABC U ABA U BAB U BCB U CBA U CBC

Simplifying it:

AB(C U A) U B(AB U CB) U CB(A U C)

I'm not entirely sure if I'm doing it right as I find out that I'm brute forcing. I'm terrible at deriving regular expressions so I'll appreciate some corrections.

$\endgroup$
  • $\begingroup$ You consider only sequences for exactly three consecutive positions. Also, it seems the knob can stay in the same position for several seconds, it seems. $\endgroup$ – Hendrik Jan Oct 31 '17 at 9:56
1
$\begingroup$

Here's a rough sketch: let $S_a, S_b, S_c$ be the set of valid strings of the language starting with $a, b, c$ respectively. Observe that:

$\qquad S_b = ((a^* + c^*)b)^*$

Furthermore:

$\qquad S_a = aS_a + bS_b$

and symmetrically for $S_c$. Therefore we may replace $S_b$ in the latter, obtaining a "recursive" equation solvable by Arden's lemma.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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