1.2. introduction to automata theory

Introduction to automata theory. What is automata theory? why it is named so? History of Automata theory

1. Introduction to Automata Theory Sampath Kumar S, AP/CSE, SECE

2. What is Automata Theory? Study of abstract computing devices, or “machines”. Automaton = an abstract computing device Note: A “device” need not even be a physical hardware! A fundamental question in computer science: Find out what different models of machines can do and cannot do The theory of computation Computability vs. Complexity 2 9 July 2017

3. What is Automata ? 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. Abstract: Existing in thought or as an idea but not having a physical or concrete existence. 9 July 2017 3

4. Alan Turing (1912-1954) Father of Modern Computer Science British mathematician Studied abstract machines called Turing machines even before computers existed Heard of the Turing test? 4 9 July 2017

5. Theory of Computation: A Historical Perspective 5 1930s Alan Turing studies Turing machines Decidability Halting problem 1940-1950s “ Finite automata ” machines studied Noam Chomsky proposes the “ Chomsky Hierarchy ” for formal languages 1969 Cook introduces “intractable” problems or “ NP-Hard ” problems 1970- Modern computer science: compilers , computational & complexity theory evolve 9 July 2017

6. Languages & Grammars Languages : “ A language is a collection of sentences of finite length all constructed from a finite alphabet of symbols ” Grammars : “ A grammar can be regarded as a device that enumerates the sentences of a language ” - nothing more, nothing less N. Chomsky, Information and Control, Vol 2, 1959 6 Or “ words ” Image source: Nowak et al. Nature, vol 417, 2002 9 July 2017

7. The Chomsky Hierarchy: 7 Regular (DFA) Context- free (PDA) Context- sensitive (LBA) Recursively- enumerable (TM) A containment hierarchy of classes of formal languages 9 July 2017

8. Finite State Machine: An automaton with a finite number of states is called a  Finite Automaton (FA) or  Finite State Machine  (FSM). 9 July 2017 8

9. Formal definition of a FSA: 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). Note : δ is called Delta and ∑ is called Sigma 9 July 2017 9

10. Some FSA Terminologies: Alphabet: 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  alphabets 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} 9 July 2017 10

11. Terminologies Cont..,: 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  ε ) 9 July 2017 11

12. Terminologies Cont..,: Kleene Star/Closure: Definition  − The set  ∑ *  is the infinite set of all possible strings of all possible lengths over  ∑  including  λ . Representation  − ∑ *  = ∑  ∪ ∑ 1  ∪ ∑ 2  ∪……. Example  − If ∑ = {a, b}, ∑ * = { λ, a, b, aa , ab , ba , bb,………..} Kleene Plus/Positive Closure: Definition  − The set  ∑ +  is the infinite set of all possible strings of all possible lengths over  ∑  excluding  λ . Representation  − ∑ +  = ∑  ∪ ∑ 1  ∪ ∑ 2  ∪……. ∑ +  = ∑ *  − { λ } Example  − If ∑ = { a, b } , ∑ +  ={ a, b, aa , ab , ba , bb,………..} Note: λ - Lambda 9 July 2017 12

13. Terminologies Cont..,: 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 , bb, ba , bb} 9 July 2017 13

14. Finite Automaton classification: Finite Automaton can be classified into two types − Deterministic Finite Automaton ( DFA ) Non-deterministic Finite Automaton ( NDFA / NFA ) 9 July 2017 14