Module 2 - What is Automata.pdf

What is Automata Theory? Arnold B. Galve, MIT, DITc [email protected] 1 What is Automata Theory? Study of abstract computing devices, or “machines” Automaton = an abstract computing device Note: A “device” need not even be a physic...

What is Automata Theory? Arnold B. Galve, MIT, DITc [email protected] 1 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 Alan Turing (1912-1954) Father of Modern Computer Science English mathematician Studied abstract machines called Turing machines even before computers existed Heard of the Turing test? 3 Theory of Computation: A Historical Perspective 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 4 The Chomsky Hierachy A containment hierarchy of classes of formal languages Regular Context- (DFA) free Context- Recursively- (PDA) sensitive enumerable (LBA) (TM) 5 The Central Concepts of Automata Theory 6 Alphabet An alphabet is a finite, non-empty set of symbols We use the symbol ∑ (sigma) to denote an alphabet Examples: Binary: ∑ = {0,1} All lower case letters: ∑ = {a,b,c,..z} Alphanumeric: ∑ = {a-z, A-Z, 0-9} Numeric: ∑ = {0,1, 2, 3,.. 9} DNA molecule letters: ∑ = {A,C,G,T} Initials of my name: ∑ = {A, B, G} Octal numbers: ∑ = {0, 1, 2, 3, 4, 5, 6, 7} Arbitrary: ∑ ={a, b, c} 7  Strings A string or word is a finite sequence of symbols chosen from ∑ Empty string is  (or “epsilon”) Length of a string w, denoted by “|w|”, is equal to the number of (non- ) characters in the string Let ∑ = {0, 1} e.g., x = 010100 |x| = 6 x = 01  0  1  00  |x| = 6 y = 111 |y| = 3 xy = concatentation of two strings x and y x = 010100; y = 111 xy= 010100111 |xy| = 9 8 Powers of an alphabet Let ∑ be an alphabet. ∑k = the set of all strings of length k If ∑ = {0, 1} ∑1 = {0, 1} ∑2 = {01, 00, 10, 11} ∑3 = {000, 111, 010, 101, 001, 100, 011, 110} ∑4 = {0000, 1111, 0101, 1010, 0011, 1100, …} ∑* = ∑0 U ∑1 U ∑2 U … ∑+ = ∑1 U ∑2 U ∑3 U … 9 Powers of an alphabet Let ∑ be an alphabet. If ∑ = {0, 1} ∑* = ∑0 U ∑1 U ∑2 U … ∑* = {, 0, 1, 00, 01, 10, 11, 000, 001, 010, … } ∑+ = ∑1 U ∑2 U ∑3 U … ∑+ = {0, 1, 00, 01, 10, 11, 000, 001, 010, … } 10  Languages & Grammars Languages: “A language is a collection Or “words” 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 Image source: Nowak et al. Nature, vol 417, 2002 11 Languages L is said to be a language over alphabet ∑, only if L  ∑*  this is because ∑* is the set of all strings (of all possible length including 0) over the given alphabet ∑ Examples: 1. Let L be the language of all strings consisting of n 0’s followed by n 1’s: L = {,01,0011,000111,…} 2. Let L be the language of all strings with equal number of 0’s and 1’s: L = {,01,10,0011,1100,0101,1010,1001,…} Definition: Ø denotes the Empty language Let L = {}; Is L=Ø? 12 The Membership Problem Given a string w  ∑*and a language L over ∑, decide whether or not w  L. Example: Let w = 100011 |w| = 6 Q) Is w  the language of strings with equal number of 0s and 1s? YES! 13 Finite Automata Some Applications Software for designing and checking the behavior of digital circuits Lexical analyzer of a typical compiler. Software for scanning large bodies of text (e.g., web pages) for pattern finding Software for verifying systems of all types that have a finite number of states (e.g., stock market transaction, communication/network protocol) 14 Finite Automata : Examples On/Off switch action state Modeling recognition of the word “then” Start state Transition Intermediate Final state state 15 Summary Defined alphabet  ∑ Defined string  sequence of symbols in the alphabet. Defined languages  L. Computed the length of a string. Concatenation Powers of an alphabet The empty string Applications of automata Some examples of finite automata. End of slides