Algorithms on 
Finite Automata

Part III. From Regular Expressions 
to Automata and Viceversa

by Jaime Rangel Mondragón

Facultad de Informática
Universidad Autónoma de Querétaro
División de Estudios de Posgrado

Centro Universitario
Cerro de las Campanas s/n
C.P. 76010 Querétaro, Qro.
Mexico

jrangel@sunserver.uaq.mx

Copyright  ©1999, UAQ, Facultad de Informática

Permission is hereby granted to reproduce part or all of this file for any purpose other than direct profit providing that the source is acknowledged.

This is the third of four parts on developing Mathematica code of algorithms on FA. To activate the functions needed from previous parts, open each one of them and choose the Kernel-Evaluate-Evaluate Initialization menu path. Do the same for this notebook. Note that only those functions required for part IV are marked for initialization.

11 NON-DETERMINISTIC AUTOMATA

11.1 Introduction

A non-deterministic finite automaton (NFA)  is described by a 5-tuple M=(Q, Σ, δ, (Subscript[q, 0]), F), wherein Q is a finite set of states, Σ is an alphabet, δ is the transition function δ:Q×(Σ ⋃ {ε}) →  (2^Q), (Subscript[q, 0])∈Q is the initial state and F⊆Q is the set of final states.
An NFA is an FA with missing or extra transitions; moreover an ε or "spontaneous" transition is allowed. According to Kleene´s theorem, NFA and FA are equivalent in the sense that any language accepted by an automaton of one family can also be accepted by some of the other. The usefulness of NFA comes from the ease in which the operations in section 8 of this work can be undertaken. NFA also expedite the design of automata as they naturally enhance the main features of the problem at hand and exhibit a substantial number of states less than their FA counterpart.
We will adopt a special notation to describe NFA. 
The only difference with the notation adopted previously for FA resides in the specification of δ. Instead of δ being a list of lists, for NFA δ will be a lists of lists of lists. For example, the FA aa (see section 2)
		{{{2,1},{3,1},{3,3}},{3}}
 will be written as an NFA as:
	{{{{},{2},{1}},{{},{3},{1}},{{},{3},{3}}}, {3}}
where the first elements correspond to the ε-transitions; for all FA they will be void.
It is interesting to note that a different NFA version exists for the FA aa and is given by

\(NFAaa = {{{{}, {1, 2}, {1}}, {{}, {3}, {}}, {{}, {3}, {3}}}, {3}}; 


    First[NFAaa]\  // MatrixForm\)

This latter is easier to design. Also,

suffixFA[{"aba"}, 2]

can be given as an NFA:

\(NFAex1
       = {{{{}, {1, 2}, {1}}, {{}, {}, {3}}, {{1}, {4}, {}}, {{2}, {}, {}}}, {
          4}}; 

First[NFAex1]\  // MatrixForm\)

The following examples will also be used at section 11.2.2

\(NFAex2
       = {{{{3}, {2}, {4}}, {{4}, {}, {}}, {{4}, {}, {2}}, {{}, {2}, {}}}, {
          4}}; 

First[NFAex2]\  // MatrixForm\)

\(NFAex3
       = {{{{2}, {1}, {}, {}}, {{3}, {}, {2}, {}}, {{}, {}, {}, {3}}}, {3}}; 
    

First[NFAex3]\  // MatrixForm\)

11.2 From FA to NFA

FA are easily converted into NFA as they already comply with the conditions defining NFA. Function NFA below provides the new notation accomodating in the first column of δ empty ε-transitions as shown in the examples.

NFA[{δ_, F_}] := 
      Module[{x}, {
          Join[{{}}, #]& /@ 
            (δ  /.  x_Integer -> {x}), F}]

showFA[NFA[aa]]

showFA[NFA[modMxN[3, 1, 4]]]

11.3 From NFA to FA

This case turns out to be substantially more difficult than the previous one. Also, if the FA has n states, their NFA counterpart can have as much as (2^n) states, corresponding to the power set of the states in the FA and whose purpose is to keep track of all the states the NFA might be at any instance.

11.3.1 Removal of ε transitions

The first stage in converting NFA to FA is the removal of ε-transitions (i.e. the disposal of the first column of δ). We compute the transitive closure of the graph in order to simulate spontaneous movements. Examples of this procedure follow.

<< DiscreteMath`Combinatorica`

\(removeEpsilon[{δ_, F_}]
         := {Transpose[Rest[Transpose[δ]]], F}\  /; \ 
        Union[First[Transpose[δ]]] == {{}}
		\)\(removeEpsilon[{δ_, F_}] := 
      Module[{nStates, nSymbols, d = δ, g, u, closure, i, j, x, y, 
          F2}, 
		\ g = First[Transpose[d]]; 

        		{nStates, nSymbols} = Take[Dimensions[d], 2]; 
		
        u = Select[Thread[{Range[nStates], g}], 
            \((Last[#] ≠ {})\)&]; 
		
        u = Map[Distribute[{First[#], Last[#]}, List]&, u]; 
		
        g = TransitiveClosure[FromOrderedPairs[Flatten[u, 1]]] /. \ 
            Graph[x_, y_] -> x; 
	
		closure = Position[g, 1]; \ 

        		d = Transpose[Rest[Transpose[d]]]; 

	\ \ 
        Map[
		
          \(({i, j} = #; 
\ \ \ \ \ \ \ \ 
              d[[i]] = 
                Map[Union[Flatten[#]]&, 
                  Thread[{d[[i]], 
                      d[[j]]}]])\)&, 
          closure]; 
		
		
        F2 = Flatten[{F, First\ /@\ Select[closure, MemberQ[F, Last[#]]&]}]; 
        
		F2 = Union[F2]; 

	\ \ 
        Map[\ \(({d, F2} = {d, F2}\  /. \ 
                  Thread[\(\((#1 -> #2)\)&\)[Range[# + 1, nStates], 
                      Range[#, nStates - 1]]])\)&, s1]; 
		
		{d, F2}]
        \)

showFA[removeEpsilon[{(({{{2, 5}, {}, {}}, {{}, {3}, {2}}, {{}, {4}, {2}}, {{8}, {4}, {4}}, {{}, {6}, {5}}, {{}, {7}, {5}}, {{8}, {7}, {7}}, {{}, {}, {}}})),{8}}]]

showFA[removeEpsilon[NFA[aa]]]

showFA[NFAex1]showFA[removeEpsilon[NFAex1]]

showFA[NFAex2]showFA[removeEpsilon[NFAex2]]

showFA[NFAex3]showFA[removeEpsilon[NFAex3]]

11.3.2  Removal of non-deterministic transitions

Function NFAtoFA below keeps track of all states the given NFA can be in and renames them accordingly. Examples of its use follow.

\(NFAtoFA[{δ_, F_}] := 
      Module[{m, nStates, nSymbols, powerSet, u, d, F2, i}, 

        		\ {d, F2} = removeEpsilon[{δ, F}]; 

        		{nStates, nSymbols} = Take[Dimensions[d], 2]; \ 
		
        powerSet = RotateLeft[Subsets[Range[nStates]]]; 
	
		
        m = Flatten[
            Map[\((u = #; 
				
                  Table[{u, i, 
                      Union[Flatten[
                          Map[d[[#, i
                                ]]&, u]]]}, {i, nSymbols}])
                  \)&, powerSet], 1]; \ 
	
	\ \ 
        F2 = Select[powerSet, 
            \((\((#\  ⋂ \ F2)\) ≠ {})\)&]; 
	\ \ 
        m = Last\ /@\ m; 
		
        Do[
			{m, F2} = {m, F2}\  /. \ 
              powerSet[[i]] -> i, {
            i, 2\^nStates}]; 
	
		m = Partition[\ m, nSymbols]; 
		
        minimize[{m, F2}]]\)

\(m = NFA[aa]; 
showFA[m]\)showFA[NFAtoFA[m]]

\(m = NFA[{{{{1, 2}, {2}}, {{}, {1, 2}}}, {2}}]; 
showFA[m]\)showFA[NFAtoFA[m]]

The following examples were introduced at the introduction to this section:

showFA[NFAex1]showFA[NFAtoFA[NFAex1]]

showFA[NFAex2]showFA[NFAtoFA[NFAex2]]

showFA[NFAex3]showFA[NFAtoFA[NFAex3]]

11.3.3  Boolean Operations using NFA

It is known that NFA can be a valuable theoretical tool. For example, the method whereby from a given regular expression the corresponding NFA  is built (from which we  conclude the existence of a suitable FA as well) is usually done through Boolean constructs involving the assembling of NFA to create new NFA in a conceptually clear manner. Function parallelNFA below provides the parallel connection of two given NFAs. 
However, as the examples below show, the direct implementation of this theoretical tool is time consuming, which renders it inadequate for our work. For this reason we will be using instead the Boolean operations developed at section 8.

\(parallelNFA[fa1_, fa2_] := 
      Module[{d, d1, d2, F1, F2, nStates1, nStates2, nSymbols1, nSymbols2}, 

        			{d1, F1} = NFA[fa1]; 
			{d2, F2} = NFA[fa2]; 

        			{nStates1, nSymbols1} = Take[Dimensions[d1], 2]; 

        			{nStates2, nSymbols2} = Take[Dimensions[d2], 2]; 

        		\ \ {d1, F1} = {d1, F1}\  /. \ x_Integer -> x + 1; 

        			{d2, F2} = {d2, F2}\  /. \ x_Integer -> x + 1 + nStates1; 
        
			d = Join[d1, d2]; \ 
		\ \ 
        d = Join[{Join[{{2, nStates1 + 2}}, Table[{}, {nSymbols1 - 1}]]}, d]; 
        
			d = Join[d, {Table[{}, {nSymbols2}]}]; 
			
        Map[\((d[[#, 1]] = {
                  nStates1 + nStates2 + 2})\)&, F1]; 
			
        Map[\((d[[#, 1]] = {
                  nStates1 + nStates2 + 2})\)&, F2]; 
	
			
        NFAtoFA[{d, {nStates1 + nStates2 + 2}}]]\)

showFA[aa]showFA[secondB]Timing[showFA[m1 = parallelNFA[aa, secondB]]]Timing[showFA[m2 = parallel[aa, secondB]]]drawFA[m1]drawFA[m2]equivalentQ[m1, m2]

showFA[difABC]showFA[evenEvenABC]Timing[showFA[m1 = parallelNFA[difABC, evenEvenABC]]]Timing[showFA[m2 = parallel[difABC, evenEvenABC]]]drawFA[m1]drawFA[m2]equivalentQ[m1, m2]

12 REVERSE AUTOMATA

The language accepted by the reverse of an FA m is the reverse of each of the words comprising the language accepted by m. Reversing the transitions of an FA means applying the transformation: 
			Add element i to δ[[ δ[[ i, j ]], j ]]
This transformation renders an NFA. Most of the text-book examples are equivalent to their reverse, which qualify them to be considered palindromic. Automaton aa is palindromic as is shown after the definition of function reverseFA below, which provides the corresponding reversed FA.

\(reverseFA[{δ_, F_}] := 
      Module[{d = δ, nStates, nSymbols, i, j, t}, 
		
        d = d\  /. \ i_Integer -> {}; 

        		{nStates, nSymbols} = Take[Dimensions[d], 2]; \ 
		
        Do[
			
          d[[δ[[i, j
                ]], j]] = 
            Union[{i}, 
              d[[δ[[i, j
                  ]], j]]], {i, 
            nStates}, {j, nSymbols}]; 
		
        d = d\  /. \ i_Integer -> i + 1; 
		t = Table[{}, {nStates}]; 
        
	
		d = Transpose[Join[{t}, Transpose[d]]]; 
		
        PrependTo[d, Join[{F + 1}, Table[{}, {nSymbols}]]]; 
		
        NFAtoFA[{d, {2}}]]\)

showFA[aa]showFA[reverseFA[aa]]

For example, to find an FA accepting (exclusively) all words such that the second and penultimate symbol are "b"  we proceed as follows.

\(m = intersec[secondB, reverseFA[secondB]]; 
showFA[m]\)Table[acceptedWords[m, i], {i, 5}]  // TableForm

The following property applies in general:

equivalentQ[prefixFA[{"aa"}, 2], reverseFA[suffixFA[{"aa"}, 2]]]

13 THE REGULAR LANGUAGE OF AN AUTOMATA

We are interested in obtaining the regular expression corresponding to the set of accepted words of a given FA. In the following we construct a system of sets of words corresponding to each state of a given FA. Each one of these sets comprises the set of all  words that would be accepted if the FA started at the corresponding state. We will be interested in computing the set corresponding to the initial state; in order to obtain it we need to solve a system of regular equations. We will do that with the help of Arden´s lemma.

13.1 Obtaining the system

\(getSystem[δ_] := 
      Module[{d = δ, nStates, nSymbols, i, j, s, m}, 

        		{nStates, nSymbols} = Take[Dimensions[d], 2]; 
		
        m = Table["ϕ", {nStates}, {nStates}]; 
		
        s = Map[FromCharacterCode[ToCharacterCode["a"] + # - 1]&, 
            Range[nSymbols]]; \ 
		
        Do[
			
          Do[
					
            m[[i, 
                d[[i, j
                  ]]]] = 
              If[m[[i, 
                      d[[i, j
                        ]]]] == 
                    "ϕ", "", 
                  m[[i, 
                      d[[i, j
                        ]]]]<>"+"]<>
                s[[j]], {j, nSymbols}], {
            i, nStates}]; 
		m]\)

aagetSystem[First[aa]]  // MatrixForm

secondBgetSystem[First[secondB]] // MatrixForm

13.2 Solving the system

The definitions below provide a suitable formatting framework.

change[u : {"(", a__, ")"}] := 
      StringJoin[u]    /;  SyntaxQ[StringJoin[{a}]]change[u : {"(", a__, ")", "*"}] := 
      StringJoin[u]    /;  SyntaxQ[StringJoin[{a}]]change[u : {b__, "+", c__}] := "("<>StringJoin[u]<>")"\(change[a_] := a
\)glue["ϕ", b_] := "ϕ"\(glue[a_, "ϕ"] := "ϕ"
\)glue["ε", b_] := b\(glue[a_, "ε"] := a	\)\(glue[a_String, b_String] := 
      change[Characters[a]]<>change[Characters[b]]
	\)incr["ϕ", b_String] := bincr[a_String, "ϕ"] := a\(incr[a_String, b_String] := a<>"+"<>b
\)klee["ϕ"] := ""\(klee[a_String] := 
      a<>"*"\ \ \  /; 
        \((StringLength[a] == 1)\)\  || \ 
          \((\ StringMatchQ[a, "(*)"]\  && \ 
              SyntaxQ[StringJoin[StringTake[a, {2, StringLength[a] - 1}]]])
            \)	\)klee[a_String] := "("<>a<>")*"

Function regularLanguage below sets up the system, reducing previously  the given FA, marking the accepting states with ε symbols, eliminating diagonal variables first and then shrinking the matrix pivoting on the second row. Examples of its use follow.

\(regularLanguage[{δ_, F_}] := 
      Module[{d, nStates, nSymbols, i, j, k, F2, s, m, m1, c, u, v, cut}, 

        		{d, F2} = minimize[{δ, F}]; 
		m = getSystem[d]; 


        		{nStates, nSymbols} = Take[Dimensions[d], 2]; 
		
        c = Table["ϕ", {nStates}]; 
		
        c[[F2]] = "ε"; 
        \ 
		m = Transpose[Append[Transpose[m], c]]; 
		
		
        While[
			{nStates, nSymbols} = Take[Dimensions[m], 2]; 
			
          cut = Select[Range[2, nStates], 
              \((m[[#, #]] == 
                    "ϕ")\)&, 1]; \ cut ≠ {}, 
			
          i = First[cut]; 
			
          Do[
			\ \ \ \ \ \ 
            If[\((j ≠ i)\) && 
                \((m[[j, i]] ≠ 
                    "ϕ")\), 
						\ \ \ \ \ \ \ 
              u = Map[glue[
                      m[[j, i]], #]&, 
                  m[[i]]]; 

              						\ \ \ \ \ \ \ 
              Do[
							\ \ \ \ \ \ \ \ \ \ \ \ 
                m[[j, k]] = 
                  incr[m[[j, k]], 
                    u[[k]]]

                									, {k, nSymbols}]]
			, {j, nStates}]; 

          			m = Drop[m, {i}]; 
			
          m = Transpose[Drop[Transpose[m], {i}]]
	]; 

		
        While[
			\ \ \ \ {nStates, nSymbols} = Take[Dimensions[m], 2]; 
          nStates > 1, 
					
          v = Map[glue[
                  klee[m[[2, 2]]], #]&, 
              m[[2]]]; 
				
          Do[
			\ \ \ \ \ \ 
            If[\((j ≠ 2)\) && 
                \((m[[j, 2]] ≠ 
                    "ϕ")\), 
						\ \ \ \ \ \ \ 
              u = Map[glue[
                      m[[j, 2]], #]&, 
                  v]; 
						\ \ \ \ \ \ \ 
              Do[
							\ \ \ \ \ \ \ \ \ \ 
                m[[j, k]] = 
                  incr[m[[j, k]], 
                    u[[k]]]

                									, {k, nSymbols}]]

            					, {j, nStates}]; 
			m = Drop[m, {2}]; 
			
          m = Transpose[Drop[Transpose[m], {2}]]\ \ \ 
			]; 
		

        \ \ \ \ \ m = Flatten[m]; 
		m = glue[klee[First[m]], Last[m]]; 

        		If[m == "", "ε", m]]\)

regularLanguage[{{{2, 2}, {2, 2}}, {1}}]

regularLanguage[dif]

regularLanguage[evenEven]

regularLanguage[aa]

regularLanguage[secondB]

regularLanguage[oddA]

regularLanguage[modMxN[2, 1, 3]]

regularLanguage[modMxN[3, 1, 4]]

\(m = wordsFA[{"a", "bb", "aaa", "ababab"}, 2]; 

    regularLanguage[m]\)

14 THE AUTOMATA OF A REGULAR LANGUAGE

We are interested in obtaining the FA corresponding to a given regular expression. Function automata below accomplishes this through function parser, which translates the regular expression. Some of the examples that follow  include their computing time as a relative measure of their complexity.

simp[{"(", a__, ")"}] := simp[{a}]\(simp[w_] := 
      Module[{w1 = Join[w, {"+"}], i = 1, u, ans = {}}, 
	
		
        While[i ≤ Length[w1], \ 
				
          u = w1[[i]]; \(i++\); 

          				While[
            \((\(! StringQ[w1[[i]]]\))
                \)\  || \ 
              \((w1[[i]] ≠ 
                  "+")\), 
            u = serialFun[u, w1[[i]]]; \ 
            \(i++\)]; 
				AppendTo[ans, u]; \(i++\)]; 
	
		
        Fold[parallelFun, First[ans], Rest[ans]]]
	
	\)\(parser[w_String] := parser[Characters[w]]
\)\(parser[w_] := 
      Module[{st = {"("}, w1 = Join[w, {")"}], u, i, j, s}, 
		
        Map[\((
			
              Which[
				# == ")", 
					j = 0; 
					
                While[u = 
                    st[[Length[st] - j
                        ]]; \ 
                  \((\(! StringQ[u]\))\)\  || \ \((u ≠ "(")\), 
                  \(j++\)]; 
					s = simp[Take[st, \(-j\)]]; 

                					st = Drop[st, \(-1\) - j]; \ 
					
                AppendTo[st, s], 
				# == "*", 
					
                AppendTo[st, kleeneFun[Last[st]]]; 
					
                st = Drop[st, {\(-2\)}], 
				True, AppendTo[st, #]])
              \)&, w1]; 
		simp[st]]
\)\(automata[r_String, alphSize_] := automata[Characters[r], alphSize]
\)automata[{"ε"}, n_] := 
      wordsFA[{"ε"}, n]automata[{""}, n_] := wordsFA[{""}, n]\(automata[a_, n_] := 
      Module[{i, j = 1, ans = {}}, \ 
	
          Do[
			
            If[a[[i]] == "+", 
              AppendTo[ans, StringJoin[Take[a, {j, i - 1}]]]; \ j = i + 1], 
            \ {i, Length[a]}]; 
		
          AppendTo[ans, StringJoin[Take[a, {j, Length[a]}]]]; 
		
          wordsFA[ans\ , n]]\  /; \ 
        Not[MemberQ[a, "("]]\  && \ Not[MemberQ[a, "*"]]
\)\(automata[a_, n_] := 
      Module[{i, p, t, u, w}, 
		p = parser[a]; 
		
        u = First[ToCharacterCode["a"]]; 
		
        t = Table[
            \((w = FromCharacterCode[i])\) -> wordsFA[{w}, n], {i, u, 
              u + n - 1}]; \ 
		
        p = p\  /. 
            "ε" -> \ 
              wordsFA[{"ε"}, n]; 
		
        \((p\  /. \ t)\)\  /. 
          \ {parallelFun\  -> \ parallel, \ kleeneFun -> \ kleene, 
            \ serialFun -> \ serial}]\)

automata[regularLanguage[{{{2, 2}, {2, 2}}, {1}}], 2]

showFA[automata["ε", 5]]

showFA[automata["ε+a", 2]]

Timing[showFA[automata["a(a+b)*", 2]]]

Timing[showFA[automata["(a+b)(a+b)*", 2]]]

Timing[showFA[automata["baa+ab", 2]]]

Timing[showFA[automata["(a+ba*ba*b)*", 2]]]

Timing[showFA[automata["(a+b)*(a+b)*", 2]]]

Timing[showFA[automata["(a+b)*", 2]]]

Timing[showFA[automata["(a+b)*aa(a+b)*", 2]]]

Timing[showFA[automata["(a+b)*(aa+bb)(a+b)*", 2]]]

equivalentQ[aa, automata["(a+b)*aa(a+b)*", 2]]

Following the idea of the previous one, the following examples verify the functions regularLanguage and automata for invertibility applied to a variety of FAs.

\(q = aa; 
r = regularLanguage[q]\ \)Timing[p = automata[r, 2]]equivalentQ[p, q]

\(q = evenEven; 
r = regularLanguage[q]\ \)Timing[p = automata[r, 2]]equivalentQ[p, q]

\(q = mod5; 
r = regularLanguage[q]\ \)Timing[p = automata[r, 2]]equivalentQ[p, q]

q=evenEvenABC;
r = regularLanguage[q] Timing[p = automata[r, 3]]equivalentQ[p, q]

\(q = {{{2, 3, 1}, {2, 2, 2}, {2, 4, 3}, {5, 3, 4}, {6, 2, 5}, {5, 7, 
            6}, {8, 9, 2}, {1, 10, 8}, {11, 2, 9}, {12, 8, 10}, {9, 8, 11}, {
            10, 1, 12}}, {1, 4}}; 
r = regularLanguage[q]\ \)Timing[p = automata[r, 3]]equivalentQ[p, q]

q=dif;
r = regularLanguage[q] Timing[p = automata[r, 2]]equivalentQ[p, q]

\(q = modMxN[5, 0, 3]; 
r = regularLanguage[q]\ \)Timing[p = automata[r, 5]]equivalentQ[p, q]

What is the regular expression describing the set of all words that begin with "a" or end with "bab" but not both (see section 10)? Answer:

\(m1 = parallel[prefixFA[{"a"}, 2], suffixFA[{"bab"}, 2]]; 

    m2 = frameFA[{"a"}, {"bab"}, 2]; 
m = difference[m1, m2]; 

    r = regularLanguage[m]\)Timing[p = automata[r, 2]]equivalentQ[m, p]

A shorter solution:

equivalentQ[m, 
      r = automata[
          "a+ab+aab+a(a+b)*(a+bb+aab)+(ε+b(a+b)*)bab", 2]]

How can we reduce a regular expression to its shorter equivalent? This non-trivial and fascinating question will be investigated in future notebooks.