Documentation

Convert a DFA into an NFA - every DFA is (almost) automatically an NFA.

Construct the union of the 2 NFAs.

Formally, for NFAs N1 and N2 recognising the languages A and B, the union of the NFAs recognise the language A∪B = { x | x ∈ A or x ∈ B }.

Idea: Add a new start state with ε arrows leading to the two original start states, so that the machine nondeterministically "guesses" which NFA to use. The accept states are those of either of the automata.

Construct the concatenation of the NFAs, the first followed by the second.

Formally, for NFAs N1 and N2 recognising the languages A and B, the concatenation of the NFAs recognise the language A∘B = { xy | x ∈ A, y ∈ B }.

Idea: Add ε arrows from the accept states of N1 to the start state of n2, so that the machine nondeterministically "guesses" where the language of N1 ends. The accept states are those of N2.

Construct the star of the NFA, i.e. the language occuring 0 or more times.

Formally, for an NFA N recognising the language A, the star of the NFA recognise the language A* = { x_1x_2...x_k | k ≥ 0, ∀i x_i ∈ A }.

Idea: Add a new accepting start state to recognise the empty string, with an ε arrow leading to the original start state. The accept states are those of N, with ε arrows leading back to the original start state, nondeterministically "guessing" where each x_i ends.

Construct an NFA recognising the language of the regular expression.

>>> (fromRegexp (S.fromList "ab") R.Empty) `accepts` ""
False

>>> (fromRegexp (S.fromList "ab") R.Single_ε) `accepts` ""
True

>>> (fromRegexp (S.fromList "ab") (R.plus (R.Single 'a'))) `accepts` ""
False
>>> (fromRegexp (S.fromList "ab") (R.plus (R.Single 'a'))) `accepts` "aaaaa"
True

>>> (fromRegexp (S.fromList "ab") (R.Star (R.Single 'a'))) `accepts` "aaaaa"
True

>>> (fromRegexp (S.fromList "ab") ((R.Single 'a') `R.exp` 2)) `accepts` "aa"
True
>>> (fromRegexp (S.fromList "ab") ((R.Single 'a') `R.exp` 2)) `accepts` "a"
False