It is a wonder that why modern computer programming languages did not evolve the same as the pre-history language that are more of graph, symbols. Maybe it is because of English is so advanced that the early engineers would like to put their ideas in an article styles, linear, logical, actions and consequences. But Allan Turing at least from the books I read, used accepters of graph to demonstrate his solutions. From my shallow readings of graph theory, graphs tend to be non-linear, you may easily jump out of some dimensions, hit a hole etc. As a reconciliation we attempted in previous blogs, I continue the technical probe of converting NFA to REX regular expressions. From here on, unless explicitly referred, most concepts are cited from book "An Introduction to Formal Languages and Automata" fifth edition, written by Peter Linz, for short, the book. At school, I read an earlier version of this book, we don't comment the book itself but try to evaluate or criticize the theories to see how it can help solving real problem in a field engineer's point of view.

The first we would refresh is the definition of regular expression, Definition 3.1 P.72 of the book.

Let $$\Simga$$ be a given alphabet. Then 1. $$\Phi$$, $$\lambda$$ and $$a \in \Simga$$ are all regular expressions. There are called primitive regular expressions. 2. If $$r_1$$ and $$r_2$$ are regular expressions, so are $$ r_1 + r_2, r_1\dot r_2, r_{1}^{*}, and \(r_1\)$$. --note probably "()" is the grouping we see in programming documentation. +, union. $$\dot$$ concatenation. * is the star closure. 3. A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2).

Previously, I used a term n-ary accepter, meant to force the graph drawer to handle all the transitions from one state to another considering the whole alphabet.The book formalize a concept of generalized transition graphs. The graph's edges are labeled with regular expressions. At the same time, the book also mentioned how to handle cycles. From my experience, it is far easy to prevent your data structure as a tree structure from entering a cycle, complex cycles, which make the graph difficult to traverse though possible by BFS or DFS. The book would suggest us to construct a complete GTG. This type of graph is a graph in which all edges are present. This may be like in graph theory books, I did not source, possibly the fully connected graph. If the universe starts from a singularity so are we all fully connected? This question asks more of a novel than of engineering. A complete GTG with n vertexes has exactly n^2 edges, and this exactly what features a fully connected graph. So for the previous graph I drew, they are not complete. So the book's guideline is to add an edge and label it with $$\Phi$$.
So next the book provides a formal procedure to simplify a complete GTG. After served by an example, we understand it is more straightforward to handle cycles or singularities when a graph is complete -- a kind of normalization to reduce the effort to handle anomolies thus the logics/gates are minimized as possible. It is a trade-off that the data are formalized as the cost, data we never fall short of them, but it takes intuition to make decision upon the fascinating frustrating reality -- lifelovehhhh. That intuition has to be fit into a container that can be considered as an autonomous computing unit. The data will always be orders higher for the container to even perceive, but the intuition is just there.

The book provides the procedure to simplify GTG by removing the nodes one by one. At the first glance, it is a scary formula but with a pratical example, it is feasible and useful. As I cite them the following, it helps better me than glancing the blank edges of the page. The book page P83.

Procedure: nfa-to-rex 1. Start with an nfa with states $$q_0,q_1,\tripledots or \ellipsis, q_n$$ and a single final state, distinct from its initial state. 2. Convert the nfa into a complte generalized transition graph. Let $$r_{ij} stand for the label of the edge from $$q_i$$ to $$q_j$$. 3. If the GTG has only two edges, with $$q_i$$ as its initial state and $$q_j$$ its final state, its associated regular expression is $$r = r_{ii}^{*}r_{ij}(r_{jj} + r_{ji}r_{ii}^{*}r_{ij})^{*}$$. (3.2) $$\equ{equ_3_2}$$ 4. If the GTG has three states, with initial state $$q_i$$, final state $$q_j$$, and third state $$q_k$$, introduce new edges, labeled $$r_{pq} + r_{pk}r_{kk}^{*}r_{kq}$$ (3.3) $$\equ{equ_3_3}$$ for $$p=i,j,q=i,j. When this is done, remove vertex $$q_k$$ and its associated edges. Note: at this step the edges to be added would be the Cartesian product of $$(i,j) \in P X Q, P,Q \subset \N, P = [1,|V|], Q = [1,|V|], (i,j) is a tuple representing one edge, |V| is the degree of the graph with node k removed.$$ 5. If the GTG has four or more states, pick a state $$q_k$$ to be removed. Apply rule 4 for all pairs of states $$(q_i,q_j), i \neq k, j \neq k$$. At each step applying the simplifying rules $$ r + \Phi = $$, $$ r \Phi = \Phi $$, $$ \Phi_{*} = \lambda$$, wherever possible. When this is done, remove state $$q_k$$. Note: the second rule is odd, it is not a union, but a concatenation, it is like your travel plan connects three freeways, one of them is blocked, so this plan is blocked, another is another. 6. Repeat Steps 3 to 4 until the correct regular expression is obtained.

Come with the book, there are some examples. But to construct complete GTG from Fig-3 in blog 201509 is almost not possible manually. So I remembered how I started the project from scratches and testing, we can simplify the model by ignoring the anomalies. It is very compact for the logic to just find the first return just after even count of quotes. This leads our alphabet to $${o,n,a}$$, where o is the double quote, n is return and a is a generalized character but we have to emphasize it is neither n nor a. Our accepter is then drafted as the following with three states $${q_0,q_1,q_2}$$.

Further, we construct a complete GTG as Fig-5.