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) .