Theory of Computation Automata PDF

Theory of Compuation ▪ Introduction ▪ Applications ▪ Automata Theory ▪ Representations and Basic Notations in Automata Theory 7/18/2024 Annual Review 2 Points to think ▪ What is Theory of computation – computation means processing. ▪ For every device we have a low level cal...

Theory of Compuation ▪ Introduction ▪ Applications ▪ Automata Theory ▪ Representations and Basic Notations in Automata Theory 7/18/2024 Annual Review 2 Points to think ▪ What is Theory of computation – computation means processing. ▪ For every device we have a low level calculation called as abstract machine or model. OFF STATE -----> SWITCH PUSH -----> ON STATE ▪ Abstract machine is called as Automata. If the machine implements automate in finite number of states then it is called finite automata. 7/18/2024 Annual Review 3 Introduction Automata theory is also known as the theory of computation Computation refers to the processing of input towards the output done by abstract machines or models. ▪ Automata are abstract machines used for efficient algorithm implementation. Devices change state from off to on when input is given, like a microwave oven. They facilitate implementing algorithms at a lower level. 7/18/2024 Annual Review 4 Applications Compiler translates programs from high level to low level language Lexical analyzer checks instructions against Valid or Invalid compiler rules and detects syntax or parser errors Pattern Matching Spell Check 7/18/2024 Annual Review 5  Automata Why Automata? Automata theory is used for pattern matching Automata checks valid input and spell check in applications. Pattern matching involves setting specific Automata detects mismatch and highlights constraints for passwords during registration. errors for invalid input Automata theory is also used for spell check Automata divides input into tokens and functionality in applications. applies rules for validity Automata theory checks for valid input. Automata detects mismatch and highlights errors for invalid input Automata divides input into tokens and applies rules for validity 7/18/2024 Annual Review 6  Automata 3 main terms(automaton, Automata theory is about abstract computability, and complexity) machines for efficient algorithm implementation. Automaton involves developing a model for Finite automata involves implementing processing input and giving output automata with a finite number of state steps. Computability checks if the machine can The applications of automata theory and accept and process input. central concepts like automaton Complexity focuses on accepting optimal development, computability, and complexity solutions are important. 7/18/2024 v Annual Review 7 Representations and Basic Notations in Automata Theory  Basics of Automata Symbols –a,b,c 0,1,2 Alphabet- Σ -Collection of symbols Σ={a,b} Σ={0,1} String – Collection of Symbols over alphabet E.g Σ={a,b} then string should be a,b,aa,ab,aab,bab,…….. Language – Collection or set of all strings over alphabet L={a,b,aa,ab,aab,bab,……..} 7/18/2024 Annual Review 9  Basics of Automata Power of an alphabet ❖ Σ ={ε} epsilon 0 ❖ Σ = Set of all strings of lenth k k ❖ Σ = Σ UΣ UΣ UΣ U * 0 1 2 3 ….. ❖ Σ = Σ UΣ UΣ U + 1 2 3 ….. 7/18/2024 Annual Review 10  Basics of Automata Kleen Closure or Kleen Star Closure – Σ* - Universal set Σ* =UΣi Σ* = Σ0UΣ1UΣ2….. Σ0 means length of string is 0 Null String or empty string {ε} epsilon Σ1 means length of string is 1 {a,b} 2 Σ means length of string is 2 {aa,ab,ba,bb} 7/18/2024 Σ* ={ε,a,b,aa,ab,ba,bb} Annual Review 11  Basics of Automata Kleen plus closure or Positive Closure – Σ+ Σ* =UΣi Σ+ = Σ+- {ε} Σ + = Σ +- Σ 0 + 1 2….. Σ = Σ UΣ Example: Language accepts strings with length 2 over Σ={0,1} L={00,10,01,11} IF Length 3 then L={000,001,010,011,100,101,110,111} if length>=2 then it will be infinite language. Note:A string is generally denoted as w and the length of a string is denoted 7/18/2024 Annual Review 12 as Iwl  Basics of Automata + and * Basic Properties of Σ Σ += * Σ {ε}UΣ * + + Σ ∩Σ = Σ * + * Σ UΣ = Σ 7/18/2024 Annual Review 13  Basics of Automata * Language => L⊆ Σ L1= *-> Universal Language Σ Lets define a language which consists of one or L2= + * Σ ⊆Σ more 0s and no 1s using the string given. L3={ n/n>=1}={0,00,000,……} * 0 ⊆Σ L4={ n n /n>=1}={01,0011,000111,……} * 0 1 ⊆Σ Now Lets define a language which consists of equal no of 0s and 1s using the string given. 7/18/2024 Annual Review 14  Basics of Automata Empty, finite and infinite languages 1. L={}= ∅ which doesn't even contain ε |L|=0 (size of the set is 0) 2. Finite Language-> |L| (if number of strings in language is finite ) 3. Infinite Language-> |L| (if number of strings in language is not finite Example of finite language L={w| |w| Finite Language |L|=8 7/18/2024 Annual Review 15 GRAMMA R Let’s dive in  Grammar G=(V,T,S,P) ▪ V=> Set of variable or Non-terminal Symbols ▪ T=> Set of terminals ▪ S=> Start Symbol ▪ P=> Production Rules 7/18/2024 Annual Review 17