11
$\begingroup$

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in this case:

enter image description here
[source]

The overlapping cycles make it hard to see what this automaton accepts (in terms of regular expressions). Is there a trick?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 23 '12 at 9:11

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ It would be good if you could indicate in the diagram what the initial and final states are: a small arrow to the initial state and a double circle as the final state. Also, it is hard to know where you are going wrong if you don't give any indication of what you have tried. $\endgroup$ – Dave Clarke Mar 23 '12 at 9:18
  • $\begingroup$ Perhaps this document can help you: it clearly explains how to convert a NFA to a RE. $\endgroup$ – Vor Mar 23 '12 at 9:34
  • 1
    $\begingroup$ Why is it hard? Have you tried one of the canonical algorithms? What is the best ansatz you can do? $\endgroup$ – Raphael Mar 23 '12 at 9:40
  • 3
    $\begingroup$ I edited to make the question (imho) interesting and good for this site. See the revision history to form an opinion. $\endgroup$ – Raphael Mar 23 '12 at 10:33
  • 1
    $\begingroup$ I have an answer ready that transforms your NFA into a regular expression, but I deleted it: Raphael's answer gives you the method you need to do it yourself (it also gives a link to an example), so you can get some practice if you want. If you still want my solution, I will undelete my answer. $\endgroup$ – Alex ten Brink Mar 23 '12 at 13:59
5
$\begingroup$

Rather than "reading off" you should employ one of several canoncial methods to do this. By far the nicest I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma (a needed result) is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

In short: For every state $q_i$, create the equation

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q_i \overset{a}{\to} q_j$ means there is a transition from $q_i$ to $q_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

Solving it (using Arden's Lemma) yields one regular expression $Q_i$ for every state that describes exactly those words that can be accepted starting in $q_i$; therefore $Q_0$ (if $q_0$ is the initial state) is the desired expression.

Application to the given automaton is left as an exercise; a complete example is included in above linked document.

See also here where I posted a similar answer.

$\endgroup$
3
$\begingroup$

If there was just a chain of states with no loop, would you know what to do?

If there was a simple loop without this overlapping branching, would you know what to do?

(If the answer is “no”, think about these cases first.)

Now, the idea is to transform the automaton progressively to put it in a form where you can spot those patterns: chains, loops, and diverging paths that reconverge in the end (leading to alternation). At every step of the transformation, take care that the transformed automaton still recognizes the same language.

Keep in mind that this is a non-deterministic automaton. The one you posted happens to be deterministic, but it doesn't have to stay that way when you transform it.

Since the sticky point is that $q_2$ can be reached from two different points, split it in two. Keep $q_1 \xrightarrow{f} q_2 \xrightarrow{g} q_3$, remove the transition from $q_4$ to $q_2$ and add instead a new state $q_5$ with transitions $q_4 \xrightarrow{j} q_5 \xrightarrow{g} q_3$. Now you should be able to spot a pattern.

If you still have trouble at this point, notice that the loop involving $q_3,q_4,q_5$ corresponds to a simple regular expression. When you get to $q_3$, you can make as many runs around this loop as you like. In some sense (which can be made technical), you can replace the state $q_3$ by the regular expression $(hjg)^*$.

Take care to check which states are final. It can help to not worry about this at first and make one big loop, then duplicate parts that terminate partway through the loop.

This is not necessarily the most efficient technique or the one that generates the simplest regular expression, but it's simple.

$\endgroup$
3
$\begingroup$

Split q_1

$\endgroup$
  • $\begingroup$ And this answers the question how? $\endgroup$ – Raphael Mar 23 '12 at 14:39
  • 1
    $\begingroup$ If you rewrite the state machine this way, it is now trivial to read the equivalent regular expression. $\endgroup$ – Jukka Suomela Mar 23 '12 at 14:40
  • 1
    $\begingroup$ Maybe you should include this in the answer text. Does this always work? $\endgroup$ – Raphael Mar 23 '12 at 14:52
  • $\begingroup$ @Raphael: It works in this case. :) The general idea behind this trick is the following: we made the cycles "properly nested". That is, we do not have the cycle structure [(]) but [()]. $\endgroup$ – Jukka Suomela Mar 23 '12 at 14:58

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.