1
$\begingroup$

enter image description here

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression.

On inspecting the given automata, I started deducing the expressions that it accepts and tried to find a pattern, and this is what I was able to figure out -

The automata makes the following transitions to a final state upon said input -

  1. $q_1 to \ q_3$ on input of a single symbol $b$, $a^*b$, $ba^*$, or $a^*ba^*$.
  2. Traversing through the cycle $q_1,q_3,q_2$ (and so on repeating) on input of $(a^*b^4a^*)^*$, a $((a^*b)^4)^*$.

Now the equivalent regular expression must be the sum of all these expressions,

R = $b + (a^*b) + (ba^*) + (a^*ba^*) + (a^*b^4a^*)^* + ((a^*b)^4)^*$.

Is there a better, concise expression for this or am I missing something? If not, How do I approach the simplification process of this expression?

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can simplify $R$ to $(a^\ast b a^\ast)(b a^\ast b a^\ast b a^\ast)^\ast$. Intuitively, this means you can loop in $q_1$ with $a$s, move to $q_3$ with $b$ and loop there again with $a$. After that you have the option to move to $q_2$ and $q_1$ via $b$ again with $a$-loops in between as often as you want. I think this the most straight forward expression. However, you should checkout at least one algorithm, e.g. Floyd-Warshall, for these kind of exercises. $\endgroup$ – ttnick Mar 1 '18 at 9:56
  • $\begingroup$ Thank you so much! Yes I just learnt Floyd-Warshall's algorithm, also realised its too expensive, and also learnt State elimination, to get the resultant regular expression much easier. $\endgroup$ – Vishhvak Srinivasan Mar 1 '18 at 10:39
  • $\begingroup$ The essence of the state elimination algorithm is quite the same. I think the recursion step is somehow "rolled over" as in Floyd-Warshall. Maybe one more trick for state elimination, since it is not taught everywhere: Instead of $(Q, \Sigma, \Delta, q_0, F)$ look at $(Q \cup \{q_s, q_f\}, \Sigma, \Delta \cup \Delta^\prime, q_2, \{q_f\})$ with $(q_0, \varepsilon, q_0) \in \Delta^\prime$ and $(p, \varepsilon, q_f) \in \Delta^\prime$ for all $p \in F$ and eliminate all states execept for $q_s, q_f$. You will get an automaton with only one transition with the desired regular expression. $\endgroup$ – ttnick Mar 1 '18 at 11:07
  • $\begingroup$ @PHPNick Yes. I think I read something similar to this in Mr.Ulmann's Book for Automata & Languages. Thank you so much for the input! $\endgroup$ – Vishhvak Srinivasan Mar 2 '18 at 4:27
2
$\begingroup$

Your DFA accepts the language of all words over $\{a,b\}$ in which the number of $b$s is of the form $3n+1$ (i.e., it is equivalent to 1 modulo 3). More generally, upon reading a word $w$, the DFA will be in state $q_1$ if it read a number of $b$s which is a multiple of 3; in state $q_3$ if it read a number of $b$s which is equivalent to 1 modulo 3; and in state $q_2$ if it read a number of $b$s which is equivalent to 2 modulo 3.

Using this description, it is easy to come up with a regular expression equivalent to your DFA. Rather than do that, let me give regular expressions for the language $L_{even}$ of words over $\{a,b\}$ containing an even number of $a$s, and for the language $L_{odd}$ of words over $\{a,b\}$ containing an odd number of $a$s:

  • $L_{even}$: $b^*(ab^*ab^*)^*$.
  • $L_{odd}$: $b^*ab^*(ab^*ab^*)^*$.

These examples should enable you to solve your specific problem.

|cite|improve this answer
$\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.