COMP 403 Formal Languages and Automata Lecture 01 PDF

COMP 403 Formal Languages and Automata Regular Languages Lecture 01 1 Instructor: Dr. Mohamed El Halaby [email protected] TA: Hagar Sobhy  Textbook Introduction to the Theory of Computation 3rd Edition by Michael Sipser Dist...

COMP 403 Formal Languages and Automata Regular Languages Lecture 01 1 Instructor: Dr. Mohamed El Halaby [email protected] TA: Hagar Sobhy  Textbook Introduction to the Theory of Computation 3rd Edition by Michael Sipser Distribution of Grades 10% Midterm ‫مفيش إعادة للمتغيبين‬ 30% Lab work (quizzes) 60% Final exam  Course Outline Computability Theory 1930s – 1950s - What is computable… or not? - Examples: Complexity Theory 1960s – program verification, mathematical truth present - Models of Computation: - What is computable in practice? Finite automata, Turing machines, … - Example: factoring problem - P versus NP problem - Measures of complexity: Time and Space - Models: Probabilistic and Interactive 2  Course Expectations Prerequisites Prior substantial experience and comfort with mathematical concepts, theorems, and proofs. Creativity will be needed for psets and exams. 4 Let’s begin: Finite Automata 0 𝑀1 1 0,1 1 𝑞1 𝑞2 𝑞3 0 Input: finite string States: Output: Accept or Reject 1 Computation process: Begin at start Transitions: state, Start state: read input symbols, follow corresponding transitions, Accept states: Accept if end with accept state, Reject if not. Examples: 01101 → Accept 00101 → Reject Say that is the language of andaccepts exactly thoseand that recognizes strings in.where that contains substring 6  Finite Automata – Formal Definition Defn: A finite automaton is a 5-tuple finite set of states finite set of alphabet symbols transition function Example: a start state means 𝑞 𝑟 𝑀1 0 1 0,1 set of accept states 𝑞1 𝑞2 1 𝑞3 0 𝛿=¿ 0 1 7 Finite Automata – Computation Strings and languages - A string is a finite sequence of symbols in - A language is a set of strings (finite or infinite) - The empty string ε is the string of length 0 - The empty language is the set with no Recognizing languages strings - - is the language of - recognizes Defn: accepts string each if there is a sequence of states where: - Defn: A language is - for regular if some - finite automaton recognizes 8 Regular Languages – Examples 0 𝑀1 1 0,1 1 𝑞1 𝑞2 𝑞3 0 More examples: Let has an even number of 1s Therefore is regular is regular (make automaton for practice). Let has equal numbers of 0s and 1s is not regular (we will prove). Goal: Understand the regular languages 9  Regular Expressions Regular operations. Let be languages: - Union: or - Concatenation: and - Star: each for Note: always Regular expressions - Built from , members [Atomic] - By using [Composite] Example. Let good, bad and boy, girl. - {good, bad, boy, girl} Examples: - {goodboy, goodgirl, badboy, badgirl} - gives all strings over - {, good, bad, goodgood, goodbad, badgood, - gives all strings that end with 1 - all strings that contain 11 badbad, goodgoodgood, Goal: Show…finite goodgoodbad, } automata equivalent to regular expression 10  Closure Properties for Regular Languages Theorem: If are regular languages, so is (closure under ) Proof: Let recognize recognize Construct recognizing should accept input if either or accept. 𝑀 1Check-in Components of : 1.1 𝑞 𝑀 In the proof, if and are finite and ? automata where has states and has states𝑞 ,𝑟 𝑀 2 Then how many states does have? (a) 𝑟 NO! [gives intersectio (b) (c) Check-in 1.1 11  Closure Properties continued Theorem: If are regular languages, so is (closure under ) Proof: Let recognize recognize Construct recognizing 𝑀1 𝑀2 should accept input if where 𝑀 accepts and accepts. 𝑤 𝑥 𝑦 Doesn’t work: Where to split ? 12  Quick review of today 1. Introduction, outline, mechanics, expectations 2. Finite Automata, formal defi nition, regular languages 3. Regular Operations and Regular Expressions 4. Proved: Class of regular languages is closed under 5. Started: Closure under , to be continued… 13 MIT OpenCourseWare https://ocw.mit.edu 18.404J Theory of Computation Fall 2020 For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.