CLASS 13 : CONSTRUCTION OF FINITE AUTOMATA (FA)

In this post we are going to learn how to construct finite automata (FA). CONSTRUCTION OF FINITE AUTOMATA (FA) means design a machine which can accept a variety of combination of input string i.e 0/1.

Input String such as :10,100,1100,10000,1010110 etc.

Learn More About Finite Automata (FA)

Let we understand by the help of examples:

1. Construct a DFA which accept string of 0's and 1's end with substring 00.


Solution: 

Here string end with 00 means those string whose last two bits are 00 such as 100,1000, 1100, 101100, 110100 etc.

Now For CONSTRUCTION OF FINITE AUTOMATA (FA) we design a machine that can accept the above strings such as 100,1000, 1100, 110100, 100100, etc.

Let first we take Input strings in different cases. 

CASE I: Input Sting =00

 CASE II: Input Sting =000

               

CASE III: Input Sting =1000    OR   1100    OR    111000

                 

CASE IV: Input Sting =110100 

                     

CASE V: Input Sting =100100  

                   

Now this transition graph is final which satisfy all input string ended with 00.

Formal Definition:

Q = {q0, q1, q2}

Σ = {0, 1}

q0 = q0

F = {q2}

δ ( Transition table) =

Now we get final transition table on the basis of above graph. For CONSTRUCTION OF FINITE AUTOMATA (FA) we consider different cases and in CASE V we get final graph that satisfy all type of input strings end with 00.

CLASS 12 : NDFA TO DFA CONVERSION EXAMPLE

Q = { q0, q1, q2 }

2^Q = { [φ], [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2] }

Σ = { 0, 1}

q0 = q0

F = {q2}

Draw transition graph according to above transition table.

Now Discard Unreachable states from graph ( जिन   स्टेट्स तक नहीं पहुचपा रहे है उनको हटा देना )  then we get new graph:

After Discard / Reject states the graph will be: 

Here q2 state is unreachable so discard it.

Now change the levels of states in graph :

Q  = {A,B,C}

Σ  = {0,1}

q0 = A

F = {C}

Transition Table (δ) will be :

SHORT CUT METHOD :

I already explain about short cut method For Review / देखने के लिए Click on Short Cut Method

Now the Transition table will be:

CLASS 11 : NDFA TO DFA CONVERSION (Short Cut Method)

Let we discuss about Short cut method for NDFA to DFA conversion.
we consider a graph given below

Q = {[φ] , [q0], [q1], [q2], [q0, q1], [q0, q2], [q1, q2], [q0, q1, q2]}

Σ = {0, 1}

q0 = q0

F = [q0]

Now write [φ] to any other suppose E

CLASS 10 : NDFA TO DFA CONVERSION

Let we understand the conversion of NDFA TO DFA.

We have a graph given below :

Note :
           Consider each element of power set of Q Non Deterministic Automata (NDFA) as a single state of deterministic automata (DFA).

Things to be remember :

{ q0 q1}→ curly braces are used for saperate elements.
[ q0 , q1]→ This is an single elements and formed by one or more state so here we use square bracket.

Formal Definition :

Q  = {q0, q1, q2 }
       i.e 2^Q = {[φ] , [q0] , [q1] , [q2] , [q0,q1] , [q0,q2] , [q1,q2] , [q0,q1,q2]}
Σ   = {0,1}
q0 = q0
F   = {q2}

Construct a graph on the basis of above transition table :

In the above graph we will discard / reject some states because they are unreachable. such as [φ] , [q1] ,  [q0,q2] , [q0,q1,q2] we get new graph.

Now write formal definition according to above graph and transition table.

Formal Definition :

Q = {[φ] , [q0] , [q1] , [q2] , [q0,q1] , [q0,q2] , [q1,q2] , [q0,q1,q2] }

Σ = {0,1}

q0 = q0

F = {[q2] , [q0,q2] , [q1,q2] , [q0,q1,q2]}   because each state contain final state i.e q2

Now do some modification in above diagram explain below :

Step 1. Discard those state which are unusable such as [φ] , [q1] ,  [q0,q2] , [q0,q1,q2] show in the above diagram shown by (X) sign.
[φ] is rejected state. 
We discard these states because we can not reach in these states in any condition. i.e unreachable state.There is no input symbol.
In this step we get following graph:

Step 2. Then we can change the level of state. But direction and input symbol can not be change.
We get following graph:

Q = ( A, B, C, D )
E is just like dummy edge.

Note: Edge is represented as capital letters. and Input is represented as small letters.

CLASS 9 : DFA DETERMINISTIC FINITE AUTOMATA

That finite automata which does not contain any ambiguity is called DFA (Deterministic Finite Automata).

Condition for Deterministic Finite Automata : 

1. It must have one state, one input and we get one state as output.
2. Every state have a path for every input symbol that means every state have a unique path.

Example: 

Solution :

Q = { q0 , q1 , q2 }

Σ = { 0, 1 }

q0 = q0

F = { q2 }

Note: here φ is not a member of Q.

In the above transaction table every state have only one path. That means there is no ambiguity arise so we can say that it is a case of DFA.

CLASS 8 : NDFA / NFA - EXAMPLE 2

2. Find transition function using given graph.

Q = { q0, q1, q2. q3, q4 }

Σ = { 0 , 1 }

q0 = q0

F = { q4 }

CLASS 7 : NDFA / NFA - EXAMPLE 1

1. Find transition function using given graph.

Solution:

Q = { q0, q1, q2 }

Σ =  {0, 1 }

q0 = q0

F = {q2}

CLASS 6 : NDFA / NFA Non Deterministic Finine Automata

Those finite automata which can not be determine is called NDFA.

Example:

Those finite automata which have ambiguity is called NDFA.

 Ambiguity means:  If we have multiple path for same input symbol is called ambiguity.

Here in the above figure if input is given in q1 state then it has two path q2 and q3 for selection ,so it is the case of ambiguity.

OR

We can say that if automata is in a stste {q1} and input symbol is 1 what will be the next state ? From the above figure it is clear that the next state will be the either {q2} and {q3}. Thus some machine can not determine uniquely by the input symbol, such machine are called non-deterministic automata.

Formal Definition:  A non- deterministic finite automata is a set of five tuples.

NFA = { Q , Σ , δ ,  q0 , F}

where ,
             Q    is a set of states
             Σ    is set of input symbols
             q0  is initial state
             F    is set of final state
             δ    is a transition function mapping from Q X  Σ into 2^Q which is power set of Q the set                     of all subset of Q. 
            
               δ : Q X Σ →  2^Q

Q ={q0, q1, q2, q3}      here Q = 4 states

2^{Q  = { [q0],[q1], [q2], [q3], [q0 q1], [q0 q2], [q0 q3], [q1 q0], [q1 q2], [q1 q3], [q2 q0], [q2 q1], [q2 q3], [q3 q0], [q3 q1], [q3 q2]}}      

CLASS 5 : FA - EXAMPLE 2

Find  whether string 0111 is accepted or not.

SOLUTION:

Here Inputs are (0111)

Since     δ = ( Q , Σ) → Q

  δ* ( q0 , 0111 )

  δ* ( δ (q0 , 0 ) , 111 ) → q1  ---------- I

  δ* ( δ (q1 , 1 ) , 11 ) → q3 -------------II

   δ* ( δ (q3 , 1 ) , 1 ) → q1 -------------III

   δ (q1 , 1 ) → q3  -----------------------IV

Note : For checking acceptance of any string means , if we get final state on inserting / giving last token or input then we say that the given string is accepted.

Here in this question string is (0111) and the last token is 1 and last transaction is IV. In IV transaction we get final state so we can say that the string (0111) is acceptable.

CLASS 4 : FA - EXAMPLE 1

1. Find whether string 011 is accepted or not in given graph. 

SOLUTION:

Here Inputs are (011)

Since     δ = ( Q , Σ) → Q

  δ* ( q0 , 011 )

  δ* ( δ (q0 , 0 ) , 11 ) → q1  ---------- I

  δ* ( δ (q1 , 1 ) , 1 ) → q3 -------------II

  δ (q3 , 1 ) → q1  ---------------------III

Note : For checking acceptance of any string means , if we get final state on inserting / giving last token or input then we say that the given string is accepted.

Here in this question string is (011) and the last token is 1 and last transaction is III. In III transaction we are not getting final state so we can say that the string (011) is not acceptable.

CLASS 3 : REPRESENTATION OF FINITE AUTOMATA

Finite automata are represented by a diagram called transaction diagram.
Transaction diagram are directed graph .
Those graph which have some direction are called directed graph.

Like:

Graph is a set of vertices and edges.

Following symbols are used in graph.

Transaction diagram are weighted diagram.

here  a is weight or level of edge.

δ : S1 X a → S2

         or

δ (S1, a) →S2

here : S1 is initial state. a is input and reaches on the next state S2.

EXAMPLE:

figure -1

here: 

Q = { q0, q1, q2, q3 }

Σ = { 0 , 1 }

q0 = q0 (initial state) it is unique in graph.

F = { q3 }

δ = Transaction function are represented by table called transaction table or by transaction graph.

Description of how to create above transaction table from graph figure-1:

here we draw matrix of transaction states and input. Write all transaction state in left side and write all inputs in the top of matrix. Now we will find and write transaction states inside the matrix on the basis of all transaction states and inputs. First we start from initial state i.e q0, we will take (q0,0) combination that means if we give 0 input to q0 state new will be q1 (or we reach on q1 state) same as if we give 1 input to q0 state new will be q2 (or we reach on q2 state) same procedure is done in all remaining states and now we get above transition table.

In Hindi:

यहां हम ट्रांजेक्शन स्टेट्स और इनपुट का मैट्रिक्स बनाते हैं। सभी ट्रांजेक्शन स्टेट्स को बाईं ओर लिखें और मैट्रिक्स के शीर्ष में सभी इनपुट लिखें।  अब हम सभी ट्रांजेक्शन स्टेट्स और इनपुट्स के आधार पर मैट्रिक्स के अंदर ट्रांजैक्शन स्टेट्स ढूंढेंगे और लिखेंगे। पहले हम आरंभिक अवस्था यानी q0 से शुरू करते हैं, हम (q0,0) संयोजन लेंगे अर्थात यदि हम q0 को नया इनपुट देते हैं तो नया q1 होगा (या हम q1 स्टेट् में पहुँचते हैं) जैसे कि हम q0 स्टेट् में 1 इनपुट देते हैं नया q2 होगा (या हम q2 स्टेट् पर पहुंचते हैं) सभी शेष राज्यों में एक ही प्रक्रिया की जाती है और अब हमें ऊपर दी गई ट्रांजेक्शन टेबल मिल जाएगी |

Now if don't want to create transaction graph than we simply represent in transaction table.Only the things we must represent initial state with arrow(→) and circle the final state(O) .

CLASS 2 : FINITE AUTOMATA (FA)

AUTOMATA : 

Automata stands for automatic machine. A machine which operate automatically is called automatic machine.

MACHINE : 

Machine is a device which receive input and produce output.

Machine are characterise in two types:

1. Physical machine.
2. Logical machine.

1. PHYSICAL MACHINE:  

Physical machines like Fan, Washing machine, Refrigerator etc. Here we do not study about physical machine.

2. LOGICAL MACHINE: 

Logical machines are those which have logical existence. like Programs, Flowcharts, DFD's etc.

Logical machine is further characteristics into two parts such as:

 a. Machine with output.
 b. Machine without output.

a. MACHINE WITH OUTPUT : 

It is normal machine because every machine gives output.

b. MACHINE WITHOUT OUTPUT:  

Machine without output means machine only checks the validity of input that mean weather input is valid or not. (It generates only decision). Input are in the form of words or token.

INFORMAL DEFINITION OF F.A:

Informal means those definition which is define informally (means itself without any rules and regulations).

Finite Automata is an automatic machine which take input, process it and possibly generate output and have countable number of states.


FORMAL DEFINITION OF F.A:

Formal definitions are those definition which are define in terms of sets, equations and symbols.

Finite Automata is a set of five tupples or elements.

F.A = ( Q , Σ ,  δ ,  q₀  , F )

where :  Q  is a set of states
              Σ (Sigma)  is a set of Input symbols

              δ (Delta)   is a transition function / mapping

              q₀  is a Initial state
              F   is a set of final states.
Note: Initial state (q₀) will be only one or (unique) and Final state will be more then one. Example a fan have 3 states such as (rest, motion, termination)


      δ :  Q X   Σ → θ

CLASS 1 : INTRODUCTION

WORKING OF COMPILERS

The above diagram show the different working performed by the compiler in different phases such as:
1. LEXICAL ANALYSIS
2. SYNTAX ANALYSIS
3. INTERMEDIATE CODE GENERATOR
4. CODE OPTIMIZATION
5. CODE GENERATION

Compiler are used to convert high level language into machine level language.
Here whole program is broken into series of tokens.
Tokens are characters as a Input.

1. LEXICAL ANALYSIS:
In lexical analysis phase compiler check weather one input is valid or not (i.e means it check the validity of input).
Inputs are: Keywords, Identifiers, Operators, Controls etc.

2. SYNTAX ANALYSIS:
In syntax analysis phase compiler check whether syntax is correct (valid) or not. (i.e it perform grammatical checking).
Example: a = b (correct statement)
'a' is variable
'b' is variable
= is operator
ab = (Incorrect statement)
It is incorrect statement so it give syntax error.
Note: Grammar is a set of rules.

3. INTERMEDIATE CODE GENERATOR:
It is automatic processing. If we write such as
a = b + c + d + e
Our system have 3 instruction sets so if we write like above then automatically compiler take or assign temporary variables.
T1 = b + c
T2 = d + e
and perform operation.

4. CODE OPTIMIZATION:
Optimization means to minimize whether memory or time or statement.

For Example is using inline function which increase processing and minimize time because it convert calls into their definition which will enhance the processing speed.
Other Example is using return statement in any function such as:

main()
{
-------
-------
-------
return();
-------
-------

It show how tends to get your output.

5. CODE GENERATION:
Here in this phase object code is generated into machine level language.

SYMBOL TABLE MANAGEMENT:
Symbol table contains the information like the type of variable and other information.

ERROR HANDLING:
Since all the phases generates the error so this phase handle the errors.
Example:
( a + b
The above statement gives error,right parenthesis is missing, either we remove the left parenthesis or we add the right parenthesis.
So all these type of error are handle by this phase.

There are following tools are applied in the above phases:
1. FINITE AUTOMATA (FA)
2. GRAMMAR
3. PUSH DOWN AUTOMATA
4. TURING MACHINE