Application of Automata Theory
Automata theory plays an important role in so many vital areas. For instance; finite automata are used in text processing, compilers and hardware design.
Also context free grammar (CFGs) which was used in the study of the human language but now used in programming languages and artificial intelligence applies automata theory.
To add to the above automata theory is also applied to the field of biology. A common example is John Conway’s way of life. Some other examples of automata theory application to biology include mollusk and pine cones growth and pigmentation patterns.
However this study considers application of automata theory to text Search.
An Application: Text Search * Finding Strings in Text
Searching Google for a set of words is equivalent to just finding strings in documents. Finding strings in text has been a common problem in the age of the web and other online text repositories (i.e given a set words, find all documents that contain one or all of those words). A search engine (such as Google) is a typical example of this process. The technology used by these search engines is inverted indexes. Many applications are unsuited for inverted indexes because i. Indexes take space which may or may not be available ii. They take very large amount of time for crawlers (a program that collects online documents) to copy the web and set up the indexes. iii. And inverted indexes do not make use of finite automata

Applications that uses automaton based techniques for searches must have the following characteristics; i. The repository on which the search is conducted should be rapidly changing ii. The document to be searched cannot be catalogued.
Typical examples of the above characteristics is a news analyst who searches the days online news articles for relevant topics (i.e a financial analyst might search for the profit a specific company makes in a year) and amazon.com does not allow crawlers to find all the pages for all the books that the company sells respectively.

Nondeterministic finite automata for text search (NFA).
Assuming we are given a set of words which we shall call keywords and we want to find occurrences of any of these words. In such applications, it is useful to design a nondeterministic finite automaton which signals by entering an accepting state that it has seen one of the keywords. The text of a document is fed one character at a time to this NFA which then recognizes occurrences of the keyword in this text. A transition diagram implemented in an NFA is designed based on the following rules; i. There is a start state with a transition to itself on every input symbol. ii. For each keyword say a1 to an there are n states say s1 to sn i.e there is a transition from the start state to s1 on symbol a1 and so on. The state sn is an accepting state and indicates that keywords a1 to an has been found,

A simple example --- find the DFA equivalent to the following NFA which searches words of x1 = ab and x2 = b in long text strings a, b
2
Start b a, b
$20
4 a
1
a, b
$20
3 b a, b
2
Start b a, b
$20
4 a
1
a, b
$20
3 b Suppose we want to use an NFA to search for the two keywords ‘Web’ and ‘eBay’ among text

2 start 3 e
$20
4 b w
1
6
7
$20 8
5
e b a y

2 start 3 e
$20
4 b w
1
6
7
$20 8
5
e b a y

∑ = set of all printable ASCII characters
∑ = set of all printable ASCII characters

From the above transition diagram, * State 1 is the start state * ∑ stands for a set of all printable Ascii Characters * State 2 through to 4 have the job of recognizing the keyword web * State 5 through to 8 recognizes eBay How to implement an NFA i. Write a program that simulates the above NFA by computing a set of states it is in after reading each input symbol. ii. Convert NFA to equivalent DFA using the subset construction then simulate the DFA directly. Advanced forms of UNIX grep command (egrep and fgrep) are some text processing programs that uses a mixture of the two approaches above.

* DFA to Recognize a Set of Keywords The converted DFA has an equal number of states of the original NFA (an observation). The DFA states may be constructed using the following rules: a) If q0 is start state of NFA, then {q0} is start state of DFA b) If p is a state of NFA reachable (accessible) from a path x = a1a2…am, then one state of the DFA is a set of NFA states consisting of 1. q0 2. p 3. Every other NFA states reachable from q0 by following every sub path which is a suffix of x, like ajaj+1…am. In the above way, all states in the DFA may be constructed, and then all transitions derived. 


2
Start
3
e
$20
4 b w
1
6
7
$20 8
5
e b a y



2
Start
3 e
$20
4 b w
1
6
7
$20 8
5
e b a y

S
12
Start
3
e b w e b a y
135
1
16
17 18
15
S
146
S
12
Start
3
e b w e b a y
135
1
16
17 18
15
S
146

From the above state 3 of the NFA becomes state 135 of the DFA because * start state 1 is included; * state 3 itself is reachable by the path x=we, so state 3 itself is included; * x has a suffix e by which states 1 and 5 are reachable from start state 1.
How to derive transitions * For any state of the DFA of the form {q0, p1, p2, …, pn}, and for each input symbol x, let the reached states be {r1, r2, …, rm}, then the next state is {q0, r1, r2, …, rm}.

* If no ri as above can be collected, then if the reached states from the q0 by x are {s1, s2, …, sk}, then the next state is {q0, s1, s2, …, sk}.

An example


12
Start
3
e b w e b a y
135
1
16
17 18
15
146
12
Start
3
e b w e b a y
135
1
16
17 18
15
146




From the above (1) for x=b, state 34, state 56, so state 135146 (2) for x=e, state 3, state 5, but state 15, so state 13515

A complete NFA to DFA conversion is shown below (S b e w, e.g., means all ASCII characters other than b, e, w).

From the above diagram, each of the states of the DFA is located in the same position as the state p from which it is derived (using rule (b) above). For example, let’s consider the state 135 which is a shorthand for {1, 3, 5} was constructed from state 3. It includes a start state 1 because every set of the DFA states does.
It also includes state 5 because that state is reached from state 1 by a suffix ‘e’, of the string “we” that reaches state 3 in the figure above.
The transitions for each of the DFA states may be calculated according to the subset construction. However the rule is simple. From any set of states that include the start state qo and some other state {P1, P2, … Pn} determine, for each symbol x, where the Pi’s go in the NFA and let this DFA state have a transition labeled x to the DFA state consisting of qo and all the targets of the Pi’s on the symbol x.
On all symbols x such that there are no transitions out of any of the Pi’s on symbol x lets this DFA state have a transitions on x to that state of the DFA consisting of qo and all states that are reached from qo in the NFA following an arc labelled x.
For instance, state 135 of the figure above, the NFA has a transition on symbol b from states 3 and 5 to state 4 and 6 respectively.
Therefore on symbol b, 135 goes to 146. On symbol e, there are no transitions of the NFA out of 3 or 5 but there is a transitions from 1 to 5.
Thus in the DFA, 135 goes to 15 on input e and also on input w, 135 goes to 12.
On every other symbol x there are no transitions from 135 to 1 on every symbol in ∑ other than b, e and w. The notation ∑-b-e-w is used to represent this set and also a similar representation of other sets in which few symbols are removed from ∑,

References
1. Automata theory, https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Automata_theory.html
2. John E. Hopcraf, Rajeev Motwani and Jeffery D Ullman in introduction to automata theory languages and computations.
3. Applications of automata theory, http://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/apps.html
4. How practical is automata theory, http://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory