Finite automata

What is finite automata ?

Finite Automata (FA)  is an abstract machine in the form of a mathematical model system with discrete input and output that can recognize the simplest language (regular language) and can be implemented in real terms.

FA is defined as a pair of 5 tuples : (Q, , , S, F). Q: a finite set of states∑ : a finite set of input symbols (alphabet): transition function, describes the transition of FSA states due to reading of input symbols. (Transition function is usually given in the tabular form.) S: STATE state (Start) F: a set of END (Final) states.

Characteristics of Finite Automata :

1)Each Finite Automata has finite states and transitions.

2)Transition from one state to another can be deterministic or non-deterministic.

3)Every Finite Automata always has an initial state.

4)Finite Automata can have more from one final state. if after processing the whole string, the final state is reached, it means that the automata accept the string.

Each FA  has :

• A finite set of states (state) One state is the initial state, usually expressed as q0. Several states are the final state.
• The finite set of input symbols
• Transition function Specifies the next state of each state pair and an input symbol.

How Finite State Automata Work?

Finite State Automata works by means of the machine reading the input memory in the form of a tape that is 1 character at a time (from left to right) using a read head which is controlled by a finite state control box where on the machine there are a finite number of states. Finite Automata is always in a state called the initial state when Finite Automata starts reading the tape. A state change occurs on the machine when the next character is read.

When the head has arrived at the end of the tape and the condition encountered is the final state, then the string contained in the tape is said to be accepted by Finite Automata (the strings belong to the language if it is accepted by the Finite Automata of the language). 

Finite State Diagram (FSD)
Finite State Automata can be modeled with Finite State Diagrams (FSD) which can also be called State Transition Diagrams. A transition system is a system whose behavior is presented in the form of states. The system can move from one state to another according to the input given to it. The Transition Function (d) is a mathematical representation of state transitions.
S = set of alphabets. Q = set of states. d = Q x S Q

Finite State The diagram consists of:
1. The circle represents the state The circle is labeled according to the name of the state. The division of the circle is: a. Single-lined circle means temporary state. A double-lined circle means the final state
2. Arrows represent transitions that occur. Labels in arrows represent symbols that make transitions from one state to another. 1 arrow is labeled start to indicate the start of the transition.

Example :

1. FSA to check odd parity
For example input: 1101
Even 1 Odd 1 Even 0 Even 1 Odd: accepted by the machine
For example input: 1100
Even 1 Odd 1 Even 0 Even 0 Even: rejected by the machine

Q = {Gnp, Gjl} set state∑ = {0,1} set of input symbolsδ = transition function,

S = Gnp (Start)F = {Gjl} (Final) END state set(remember for set must be written in {} )From the diagram Example Language/L(m) accepted is :0110 (because the final state is the final state , in this context it is Gjl1011 = accepted0100 = accepted11110 =accepted011 = rejected (because the final state is not in the final state, Gnp)11011 = rejected

FA based on the definition of the ability to change the state can be divided into 2, namely:

1. Deterministic (DFSA/ DFA) At each input, there is only one destination state (State) from the current state.

Mathematical notation DFA: M = name DFAQ = set of states DFAS = set of alphabets = transition function, q0 = initial state,F = final state,M = (Q, S, d, q0, F)

Example: 
Known DFA:
Q = {q0, q1, q2} δ is given in the following table:
∑ = {a, b} 
S = q0
F = {q0, q1}

The transition function is:

L (M) =  ab ababaabaa, aaaabab, aabababa,…}

Search/Tracking: Search, whether the following sentences are accepted by the DFA above: abababaa, aaaabab , aaabbaba
Answer: δ (q0,abababaa) (q0,bababaa) (q1,ababaa) ⇒ δ (q0,babaa) (q1,abaa) (q0,baa) (q1,aa) (q0,a) q0Tracking ends at q0 (END state) sentence abababaa accepted.
Conclusion: A sentence is accepted by DFA above if the tracing ends in one of the END states.

2. Non-deterministic Finite Automata (NFSA/NFA).

At each input, there is more than one destination state from the current state

Finite automata are uncertain for each pair of input states, can have 0 (zero) or more choices for the next state.

For each state, there is not always exactly one next state for every existing input symbol.

From a state, there can be 0.1 or more exit arcs (transitions) labeled with the same input symbol. 

For NFA, all possibilities must be tried until there is one that reaches the final state. 

A string x is accepted by the NFA language, M= ( Q, _, d, S, F) if {x | d(S,x) contains a state in F}

The two finite automata above are able to recognize regular sets with precision. Thus, the two finite automata can recognize the strings indicated by regular expressions correctly. DFA can lead the recognizer (identifier) ​​faster than NDFA. However, the DFA is larger than its equivalent NDFA. It's easier to build NDFA than DFA for a language, but easier to implement DFA than NDFA.
Example:
Here is an example of NFA (Q, , , S, F). where : Q = {q 0, q1 , q2 ,q3 , q4 }δ is given in the following table:
= {a, b,c}S = q0F = {q4}∑= {a, b,c}S = q0F = {q4 }

A sentence is accepted by the NFA if:

One of the trackings ends in the END state, or the set of states after reading the string containing the END state. Find out whether the following sentences are accepted by the NFA above: ab, abc, aabc, aabb.

Answer: (q0 ,ab) (q0,b) (q1 ,b) {q0, q2} {q1 } = {q0 , q1 , q2}The set of states DOES NOT contain END state sentence ab does not accepted δ(q0 ,abc) δ(q0 ,bc) δ(q1 ,bc) { (q0 ,c) (q2 ,c)}∪δ(q1 , c){{ q0 , q3 } { q2 }}∪{ q1 } = {q0 , q1 , q2 ,q3 }

The state set does NOT contain the END state ⇒ abc sentences are not accepted.

Equivalence of Deterministic Finite Automata 

For a regular language, there may be a number of Deterministic Finite Automata that can accept it. The only difference is the number of states that the equivalent automata have. Of course, for practical reasons, we choose automata with fewer states.
Our goal here is to reduce the number of states of a Finite State Automata, without reducing its original ability to accept a language.
There are two new terms that we need to know, namely:

1.  Distinguishable which means it can be distinguished.

2.  Indistinguishable which means cannot be distinguished.
Two DFAs M1 and M2 are said to be equivalent if L(M1) = L(M2)

State Number Reduction In FA Reduction is done to reduce the number of states without reducing the ability to accept a language as it was (efficiency). State in the FSA can be reduced if there is a useless state. The result of the reduced FSA is the equivalent of the original FSA.
State pairs can be grouped based on:

1.  Distinguishable State  (can be distinguished)   

The two states p and q of a DFA are said to be indistinguishable when:    δ (q, w) Î F and δ (p, w) Î F or δ (q, w) ∉ F and δ (p, w) ∉ for all w Î S*

2.  Indistinguishable State  (cannot be distinguished)   

Two states p and q of a DFA are said to be distinguishable if there is a string w S* up to:                                                  

(q,w) F and (p,w) F
Reduction of the number of states in FSA – Relation A pair of two states that is either distinguishable or indistinguishable but not both.
In this case, there is a relation: If p and q are indistinguishable, and q and r are indistinguishable, then p, r is indistinguishable and p,q,r are indistinguishable.
In evaluating the state, a relation is defined: For Q, which is the set of all states, is the set of distinguishable states. , where D QN is the set of indistinguishable states, where N Q then x N if x Q and x D
Reduction of the number of states in the FSA – Step Steps to perform this reduction are:
1. Remove all unreachable states from the initial state (useless state) 2. Make all pairs of distinguishable states (p, q) where p F and q F. List all pairs of states. Look for other distinguishable states using the following rules: For all (p, q) and all a, calculate (p, a) = pa and (q, a) = qa . If the pair (pa, qa) is a distinguishable state pair then the pair (p, q) is also a distinguishable pair. All state pairs that are not included as distinguishable states are indistinguishable states. Adjust the transitions of the merged states.
Reduction of the Number of States in the FSA
Example:

•  State q5 cannot be reached from the initial state by any means (useless state). Delete state q5
•  Record the distinguishable states, namely: q4 F while q0, q1, q2, q3 F so that the pairs (q0, q4) (q1, q4) (q2, q4) and (q3, q4) are distinguishable.
• Other distinguishable state pairs are derived based on pairs from step 2, namely: For pairs (q0,q1) (q0, 0) = q1 and (q1, 0) = q2 – not yet identified δ(q0, 1 ) = q3 and (q1, 1) = q4 – (q3, q4) are distinguishable then (q0, q1) is distinguishable. For pairs (q0, q2) (q0, 0) = q1 and (q2, 0) = q1 – not identified (q0, 1) = q3 and (q2, 1) = q4 – (q3, q4) distinguishable then (q0, q2) is distinguishable.
• After checking all state pairs, there are distinguishable states: (q0,q1), (q0,q2), (q0,q3), (q0,q4), (q1,q4), (q2,q4) , (q3,q4). Because based on the existing relations, it cannot be proven that (q1, q2), (q1, q3), and (q2, q3) are distinguishable, so it can be concluded that these state pairs are indistinguishable.
• Since q1 is indistinguishable with q2, q2 is indistinguishable with q3, it can be concluded that q1, q2, q3 are mutually indistinguishable and can be made into one state.
• Based on the results above, the results of the reduced DFA are: