Almost four years ago, I came across a CPP 2013 paper named Certified parsing of regular languages by Denis Firov, Tarmo Uustalu [1].

This paper describes a way to construct NFAs corresponding to a given regular expression using matrix operations. The underlying principle was Thompson's algorithm for NFA construction.

The CPP paper also had an agda implementation associated with it, where they expressed regular expressions using an agda type like this:

data RegExp : Set where

  -- regex for empty word
  ε   : RegExp

  -- Atom
  ′_  : Σ → RegExp

  -- Concatenation
  _○_ : RegExp → RegExp → RegExp

  -- Choice
  _∪_ : RegExp → RegExp → RegExp

  -- Kleene plus
  _₊  : RegExp → RegExp

Interestingly, they were using Kleene plus instead of the more common Kleene star as the base operation. Of course it is not that big a deal theoretically, since Kleene star and Kleene plus can be written in terms of each other. Still, I wondered why. The paper itself had this remark:

Note that instead of the Kleene star (_*) we use plus (_+). This is more convenient for us and does not restrict generality, as star is expressible as choice between the empty string and plus.

Though this makes it clear that the authors found Kleene plus more convenient, I could not figure out why it was more convenient. I tried asked around, but could not find anyone who could figure out the reason. I also tried contacting the authors, but the mail ids that I found were probably obsolete since the paper is a bit old. Anyway, after persisting a while, I gave up. A lot later, when I felt I needed a break, I tried asking this question in the proofassistants stackexchange. And the answers and comments helped me understand the reason. (Should have posted the question online, much earlier.) Let me try explaining it in my own words.

Background: McNaughton-Yamada-Thompson construction

The CPP paper builds NFAs corresponding to a given regular expression using an algorithm credited to McNaughton, Yamada and Thompson [2], [3]. There are many algorithms to convert regex to finite automaton. The McNaughton-Yamada-Thompson algorithm is probably the easiest to understand and implement. This algorithm is sometimes also called Thompson construction.

As I understand it, the original NFA construction algorithm was developed by McNaughton and Yamada [2], while Ken Thompson made the algorithm [3] which allows these NFAs to be run without converting them to DFAs. This is a great advantage since NFA to DFA conversion leads to an exponential increase in the number of states (state space explosion). Thompson's algorithm runs an NFA by simulating its execution. A description of Thompson's NFA simulation algorithm is not necessary for this blog post, so I am skipping that (See this article for more about this).

Obviously, it is desirable for automata to have as few states as possible. Because more number of states means a need for more storage space and more state-transition details to keep track of.

Finding N^* for an NFA N

A NFA consists of a set of states and transitions between those states. Some of these states are marked initial or final states. The state transitions can happen with or without input.

Let's have a look at a formal definition for NFAs.

An NFA N may be defined as a quintuple N = (Q, Σ, δ, I, F), where

Q: Finite set of states
Σ: Finite set of input symbols
δ : Q × (Σ ∪ ε) → P(Q): Transition function
I ⊆ Q: Set of initial states
F ⊆ Q: Set of final states

Definition 1 : NFA

Note that there can be more than one start state in this definition of NFAs.

Given an NFA as N_r = (Q_r, Σ_r, δ_r, I_r, F_r) corresponding to a regex r, how can we construct an NFA as N_r^* = (Q_r^*, Σ_r^*, δ_r^*, I_r^*, F_r^*) corresponding to the regex r^*?

One may be tempted to think of a construction where we add ε-transitions from each state in F_r to each of the states in I_r as shown in Figure 2.

Schematic NFA for an incorrect star operation — Figure 2 : NFA for an incorrect star operation

Such a construction is made as a copy of A with the following modifications:

Add ε-transitions from each state in F to each of the states in I.
Make the set of final states of A^* same as the set of initial states of A.

Q_{A^*} = Q_A

\Sigma_{A^*} = \Sigma_A

I_{A^*} = I_A

F_{A^*} = I_A

$\delta_{A^*}(p, \varepsilon) = {p} \cup I_A, p \in F_A$ $\delta_{A^*}(p, \sigma) = \delta_A(p, \sigma)$

Definition 2 : A wrong

N^*

construction

For example, consider an NFA N₁ shown below Figure 3. It corresponds to the regex r₁ = a.

Example derivation tree — Figure 3 : $N_1$

Constructing an NFA using construction from Definition 1 yields the automaton N₁^* shown in Figure 4.

Star NFA for NFA N1 — Figure 4 : $N_1^*$

Though this automaton really does correspond to r₁^*, this is just a coincidence and does not mean that definition the construction in Definition 1 is a correct way to derive N^* for a given N. Let us consider NFAs corresponding to a few more regexes to illustrate this.

A few incorrect N^* NFAs

Let us have a look at the NFAs corresponding to the following regexes:

Table 1 : Example regular expressions
Regex	NFA	Language
r₂ = (ab) * a	N₂	L(r₂)
r₃ = (c * ab) * c * a	N₃	L(r₃)
r₄ = (ab) * ac	N₄	L(r₄)

An NFA recognizing L(r₂) could look like this:

The corresponding NFA, say $N_2^{\#}$ , that is derived via Definition 2 would be:

Star attempt for N2 — Figure 6 : $N_2^{\#}$

Since N₂ corresponds to the regex r₂ = (ab)^*a, we want $N_2^{\#}$ to recognize the language of ((ab)^*a)^*. Yet, it is obvious that $N_2^{\#}$ accepts the word ab ∉ L(r₂^*).

Similarly, $N_3^{\#}$ (Figure 8b) accepts the word cc ∉ L(r₃^*).

Star attempt for N3 — (a) : $N_3$ (Original NFA)

Figure 8 : NFAs based on

r_3

Likewise, $N_4^{\#}$ (Figure 9b) accepts the word ab ∉ L(r₄^*).

Star attempt for N4 — (a) : $N_4$ (Original NFA)

Figure 9 : NFAs based on

r_4

In fact, the regex corresponding to $N_3^{\#}$ is (c|a(b|ε))^* and the one for $N_4^{\#}$ is ((ab)|(ac))^*. Clearly, Definition 2 is not a correct way to construct N^*. This is the construction that it suggests produces wrong results. At least in cases where there is a transition to an initial state, like in the examples of N₂, N₃ and N₄. It happened to produce a correct result in the case of N₁ since it had no transition going back to initial state.

A correct way

A robust way to produce N^* corresponding to a given N is by adding an additional state that is made to be the sole initial and final state as described below.

Q_{A^*} = \{𝟙\} \cup Q_A

\Sigma_{A^*} = \Sigma_A

I_{A^*} = \{𝟙\}

F_{A^*} = \{𝟙\}

$\delta_{A^*}(𝟙, \varepsilon) = I_A$ $\delta_{A^*}(q, \varepsilon) = I_A, q \in F_A$ $\delta_{A^*}(p, \sigma) = \delta_A(p, \sigma)$

Definition 3 : A correct

N^*

construction

N^* NFAs made using the construction shown in Definition 3, that correspond to the NFAs N₁, N₂, N₃ and N₄, are shown in Figure 10. Note that the number of states in the resultant NFA need not be minimal when using this construction. I suppose that is a cost we pay for having generality while maintaining correctness and simplicity. For example, N₁^* derived using Definition 3 has more number of states than the version in Figure 4, though both recognize the same language. This is a trade off that was chosen for having a general solution.

Consider the NFA N₂^* in Figure 10 which is the 'starred'-form of the NFA N₂ from Figure 5, which in turn corresponds to the regex r₂ at Table 1. We can partition N₂^* into two parts: one corresponding ε and the other corresponding to N₂.

Parts of N2 — Figure 11 : Decomposition of $N_2$

ie, the NFA made using construction in Definition 3 essentially corresponds to ε|r⁺.

NFA for N⁺

When compared to N^*, adjustments needed to make the N⁺ for a given NFA N is much simpler. We just need to add ε-transitions from each of the final states of N to each of its initial states as shown in Figure 11 below.

Notice that there is no need to have any extra states. The number of states needed for N⁺ is exactly the same as that of N.

Conclusion

In general, given a regex r whose NFA is N, the NFA for N^* would need at least 1 more state than N. On the other hand, the NFA for N⁺ doesn't need any additional states. And since the CPP paper already creates an NFA for ε, it is more convenient to use ε|r⁺ instead of a separate star operation. This can lead to lesser number of states in the case of large NFAs.

TL;DR: Initital state of N cannot be final state of of N^*. A new state is needed. This results in what is essentially ε|N⁺. Might as well just use N⁺.

Acknowledgements:

Li-Yao Xia: This post was triggered thanks to their answer and comments on a question that I had posted at proof assistants stackexchange
JFLAP: Just to be sure, I tried all the automata and regex mention in this post on JFLAP. It's a great tool, but it would have been better if there was a way to script it.

(This post has a lot of hand-written HTML. Please do tell me if you spot errors.)

References

[1]

D. Firsov and T. Uustalu, “Certified parsing of regular languages,” in International conference on certified programs and proofs, Springer, 2013, pp. 98–113. Available: https://cs.ioc.ee/~tarmo/papers/firsov-uustalu-cpp13.pdf

[2]

R. McNaughton and H. Yamada, “Regular expressions and state graphs for automata,” IRE transactions on Electronic Computers, no. 1, pp. 39–47, 1960.

[3]

K. Thompson, “Programming techniques: Regular expression search algorithm,” Commun. ACM, vol. 11, no. 6, pp. 419–422, Jun. 1968, doi: 10.1145/363347.363387.