Automaton

Definition of an Automaton, characteristics of automata,types of automata,deterministic finite automata,non-deterministic automata,Example of Automata,Graphical representation of DFA and NDFA. transition table and transition diagram of DFA and NDFA

1. Automata

2. Defination of Automaton Theory of Computation 1

3. Definition of an Automaton Automaton are abstract model of machine that perform computational on an input by moving through a series of state and configurations. At each state of the computation a transition function determines the next configuration on the basis of a finite portion of the present configuration . As a result ones the computation reaches an accepting configuration it accept the input. The most general and powerful automata is Turing Machine . The major objective of an automata theory is to develop method by which computer scientist can describe and analyse the dynamics behaviours of discrete system ,in which the signals are sampled periodically. The behaviour of these discrete system is determined by the way that the system is constructed from storage and combinational elements. 3

4. Model of discrete automaton X1 X2 Xn Y1 Y2 Yn AUTOMATON Q1,Q2………. Q n 4

5. Characteristics of an Automata Input: At each of the discrete instance of time t1, t2, t3, ….., tn the input values are as X 1 , X 2 , X 3 , …., X n , each of which can take a finite number of fixed values from the input alphabet ∑, are applied to the input side of the model . Output:   Y 1 , Y 2 , Y 3 , …., Y n , are the output of the discrete automata model, each of which can take a finite number of fixed values form an output Y. States:  An state is an condition of processing the inputs. At any instant of time the automaton can be in one of the states q 1 , q 2 , q 3 , ….. q n . State relation:  The next state of an automaton at any instant of time is determined by the present state and the present input. Output relation:  The output is related to either state only or to both the input and the current state. 5

6. Example of Automata : Sequential machine:  A sequential machine is a mathematical model of a certain type of simple computational structure. Vending Machines:  A vending machine is an automated machine that dispenses numerous items such as cold drinks, snacks, beverages, alcohol etc. to sales automatically, after a buyer inserts currency or credit into the machine. Vending machine is works on finite state automate to control the functions process. Traffic Lights:  The optimization of traffic light controllers in a city is a systematic representation of handling the instructions of traffic rules. Its process depends on a set of instruction works in a loop with switching among instruction to control traffic. Regular Expression Matching:  It is a technique to checking the two or more regular expression are similar to each other or not. The finite state machine is useful to checking out that the expressions are acceptable or not by a machine or not. Speech Recognition:  Speech recognition via machine is the technology enhancement that is capable to identify words and phrases in spoken language and convert them to a machine-readable format. Receiving words and phrases from real world and then converted it into machine readable language automatically is effectively solved by using finite state machine. 6

7. Automata – What is it? The term "Automata" is derived from the Greek word "α ὐτόμ ατα" which means "self-acting". An automaton (Automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite State Machine (FSM). 7

8. Formal definition of a Finite Automaton Formal definition of a Finite Automaton An automaton can be represented by a 5-tuple (Q, ∑, δ, q , F), where − Q  is a finite set of states. ∑  is a finite set of symbols, called the  alphabet  of the automaton. δ  is the transition function. q  is the initial state from where any input is processed (q  ∈ Q). F  is a set of final state/states of Q (F ⊆ Q). 8

9. Related Terminologies 9 Alphabe t Definition  − An  alphabet  is any finite set of symbols. Example  − ∑ = {a, b, c, d} is an  alphabet set  where ‘a’, ‘b’, ‘c’, and ‘d’ are  symbols . String Definition  − A  string  is a finite sequence of symbols taken from ∑. Example  − ‘ cabcad ’ is a valid string on the alphabet set ∑ = {a, b, c, d} Length of a String Definition  − It is the number of symbols present in a string. (Denoted by  |S| ). Examples  − If S = ‘ cabcad ’, |S|= 6 If |S|= 0, it is called an  empty string  (Denoted by  λ  or  ε )

10. Related Terminologies 10 Kleene Star Definition − The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the infinite set of all possible strings of all possible lengths over ∑ including λ . Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set of all possible strings of length p . Example − If ∑ = {a, b}, ∑* = { λ, a, b, aa , ab , ba , bb ,………..} Kleene Closure / Plus Definition − The set ∑+ is the infinite set of all possible strings of all possible lengths over ∑ excluding λ . Representation − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪ ……. ∑+ = ∑* − { λ } Example − If ∑ = { a, b } , ∑+ = { a, b, aa , ab , ba , bb,………..}

11. Related Terminologies 11 Language Definition  − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite. Example  − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab , aa , ba , bb }

12. Finite Automaton Finite Automaton Finite Automaton (Output) Finite Automaton with (Output) Mealy machine Moore machine N Non-deterministic Finite Automaton (NDFA / NFA ) Deterministic Finite Automaton (DFA) 12

13. Deterministic Finite Automaton (DFA) In DFA, for each input symbol, one can determine the state to which the machine will move. Hence, it is called  Deterministic Automaton . As it has a finite number of states, the machine is called  Deterministic Finite Machine  or  Deterministic Finite Automaton . Formal Definition of a DFA A DFA can be represented by a 5-tuple (Q, ∑, δ, q , F) where − Q  is a finite set of states. ∑  is a finite set of symbols called the alphabet. δ  is the transition function where δ: Q × ∑ → Q q  is the initial state from where any input is processed (q  ∈ Q). F  is a set of final state/states of Q (F ⊆ Q ). 13

14. A DFA is represented by digraphs called state diagram . The vertices represent the states. The arcs labelled with an input alphabet show the transitions. The initial state is denoted by an empty single incoming arc. The final state is indicated by double circles. Graphical Representation of a DFA Example Let a deterministic finite automaton be → Q = {a, b, c}, ∑ = {0, 1}, q  = {a}, F = {c}, and Transition function δ Transition function δ as shown by the following table − Present state N ext State for input 0 Next State for input 1 a a b b c a c b c 14

15. Graphical Representation… b 1 START a c 1 1 Present state N ext State for input 0 Next State for input 1 a a b b c a c b c 15

16. Non-deterministic Finite Automaton In NDFA, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined. Hence, it is called  Non-deterministic Automaton . As it has finite number of states, the machine is called  Non-deterministic Finite Machine  or  Non-deterministic Finite Automaton . Formal Definition of a DFA A N DFA can be represented by a 5-tuple (Q, ∑, δ, q , F) where − Q  is a finite set of states. ∑  is a finite set of symbols called the alphabet. δ  is the transition function where δ: Q × ∑ → 2 Q (Here the power set of Q (2 Q ) has been taken because in case of NDFA, from a state, transition can occur to any combination of Q states) q  is the initial state from where any input is processed (q  ∈ Q). F  is a set of final state/states of Q (F ⊆ Q). 16

17. Graphical Representation of an NDFA: (same as DFA) An NDFA is represented by digraphs called state diagram. The vertices represent the states. The arcs labelled with an input alphabet show the transitions. The initial state is denoted by an empty single incoming arc. The final state is indicated by double circles . Graphical Representation of a NDFA Example Let a Non-deterministic finite automaton be Q = {a, b, c}, ∑ = {0, 1}, q  = {a}, F = {c}, and Transition function δ Present state N ext State for input 0 Next State for input 1 a a ,b b b c a ,c c b ,c c Transition function δ as shown by the following table − 17

18. Graphical Representation… b 0,1 START a c 1 0,1 0,1 Present state N ext State for input 0 Next State for input 1 a a ,b b b c a ,c c b ,c c 18

19. Thank You 19