Definition of Finite Automata

Definition of Finite Automata:

A finite automata (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet) C. The job of an FA is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input.

A finite automaton consists of:

• a finite set S of N states
• a special start state
• a set of final (or accepting) states
• a set of transitions T from one state to another, labeled with chars in C

As noted above, we can represent a FA graphically, with nodes for states, and arcs for transitions.

We execute our FA on an input sequence as follows:

• Begin in the start state
• If the next input char matches the label then a transition from the current state to a new state, go to that new state
• Continue making transitions on each input char
  • If no move is possible then stop
  • If in accepting state, then accept

Finite Automata(FA) is the simplest machine to recognize patterns.

A Finite Automata consists of the following :

Q : Finite set of states.
∑ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

Formal specification of machine is
{ Q, ∑, q, F, δ }.

Example of Finite Automata In Term of Programming Language

Suppose you want to write a program to recognize the word “main” in an input program. Logically, your program will look something like this:

1. cin >> char
2. while (char != “m”) cin >> char
3. if (cin >> char != “a”) go to step 1
4. if (cin >> char != “i”) go to step 1
5. if (cin >> char != “n”) go to step 1
6. done

We can explain each step in this program as follows:

1. Initialization
2. Looking for “m”
3. Recognized “m”, looking for “a”
4. Recognized “ma”, looking for “i”
5. Recognized “mai”, looking for “n”
6. Recognized “main”

Each step in the program corresponds to a different place in the recognition process. We can capture this behavior in a graph

• each node in the graph represents a step in the process
• arcs in the graph represent movement from one step to another
• labels on the arcs correspond to the input required to make a transition

It is fairly straightforward to translate an FA into a program. Consider a 4-state FA to recognize “main” in a program.

• Let FA = {S,C,T,s0,F}
• S = {s0, s1, s2, s3, s4}
• C = {a,b,..z,A,B,..Z,0,1,..9,+,-,*,/}
• F = {s4}

Transitioning of States (T) as follow:

We can easily create a program from this description of the FA. We will use statement labels to represent states and goto’s to represent the meaning of an arc. (In general, goto’s are discouraged, but this is one case where their use is not only reasonable, it is quite common.) The variable “accept” is true if the FA accepts, and is false otherwise.

s: accept = false; cin >> char;
if char = “m” goto m;
if char = EOF goto end;
goto s;
m: accept = false; cin >> char;
if char = “m” goto m;
if char = “a” goto a;
if char = EOF goto end;
goto s;
a: accept = false; cin >> char;
if char = “m” goto m;
if char = “i” goto i;
if char = EOF goto end;
goto s;
i: accept = false; cin >> char;
if char = “m” goto m;
if char = “n” goto n;
if char = EOF goto end;
goto s;
n: accept = true; while (cin >> char);
end: cout << accept;

Finite Automata or Finite Automation is the first level of machine that works to match the string  and how it will be acceptible. We can imagine the lexical analysis on Finite Automata to match the token.