Theory of computation anna University ppt

Theory of computation anna University ppt

• 1.
  18.404/6.840 Intro tothe Theory of Computation Instructor: Mike Sipser TAs: - Fadi Atieh, Damian Barabonkov, - Alex Dimitrakakis, Thomas Xiong, - Abbas Zeitoun, and Emily Liu 1
• 2.
  Computability Theory 1930s– 1950s - What is computable… or not? - Examples: program verification, mathematical truth - Models of Computation: Finite automata, Turing machines, … Complexity Theory 1960s – present - What is computable in practice? - Example: factoring problem - P versus NP problem - Measures of complexity: Time and Space - Models: Probabilistic and Interactive computation 18.404 Course Outline 2
• 3.
  Course Mechanics Zoom Lectures -Live and Interactive via Chat - Live lectures are recorded for later viewing Zoom Recitations - Not recorded - Two convert to in-person - Review concepts and more examples - Optional unless you are having difficulty Participation can raise low grades - Attend any recitation Text - Introduction to the Theory of Computation Sipser, 3rd Edition US. (Other editions ok but are missing some Exercises and Problems). Homework bi-weekly – 35% - More information to follow Midterm (15%) and Final exam (25%) - Open book and notes Check-in quizzes for credit – 25% - Distinct Live and Recorded versions - Complete either one for credit within 48 hours - Initially ungraded; full credit for participation 3
• 4.
  Course Expectations Prerequisites Prior substantialexperience and comfort with mathematical concepts, theorems, and proofs. Creativity will be needed for psets and exams. Collaboration policy on homework - Allowed. But try problems yourself first. - Write up your own solutions. - No bibles or online materials. 4
• 5.
  Role of Theoryin Computer Science 1. Applications 2. Basic Research 3. Connections to other fields 4. What is the nature of computation? 5
• 6.
  Input: finite string Output:Accept or Reject Computation process: Begin at start state, read input symbols, follow corresponding transitions, Accept if end with accept state, Reject if not. Examples: 01101 → Accept 00101 → Reject accepts exactly those strings in where contains substring Let’s begin: Finite Automata 𝑀1 𝑞1 𝑞2 𝑞3 1 0,1 0 1 0 States: Transitions: Start state: Accept states: 1 Say that is the language of and that recognizes and that . 6
• 7.
  Finite Automata –Formal Definition Defn: A finite automaton is a 5-tuple finite set of states finite set of alphabet symbols transition function start state set of accept states means 𝑞 𝑟 a 𝑀1 𝑞1 𝑞2 𝑞3 1 0,1 0 1 0 0 1 𝛿=¿ Example: 7
• 8.
  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 strings Defn: accepts string each if there is a sequence of states where: - - for - Recognizing languages - - is the language of - recognizes Defn: A language is regular if some finite automaton recognizes it. 8
• 9.
  Regular Languages –Examples Therefore is regular More examples: Let has an even number of 1s is regular (make automaton for practice). Let has equal numbers of 0s and 1s is not regular (we will prove). 𝑀1 𝑞1 𝑞2 𝑞3 1 0,1 0 1 0 Goal: Understand the regular languages 9
• 10.
  Regular Expressions Regular operations.Let be languages: - Union: or - Concatenation: and - Star: each for Note: always Example. Let good, bad and boy, girl. - {good, bad, boy, girl} - {goodboy, goodgirl, badboy, badgirl} - {, good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, … } Regular expressions - Built from , members [Atomic] - By using [Composite] Examples: - gives all strings over - gives all strings that end with 1 - all strings that contain 11 Goal: Show finite automata equivalent to regular expressions 10
• 11.
  Closure Properties forRegular Languages Theorem: If are regular languages, so is (closure under ) Proof: Let recognize recognize Construct recognizing should accept input if either or accept . 𝑀2 𝑟 𝑀1 𝑞 𝑀 𝑞,𝑟 Components of : and NO! [gives intersection] Check-in 1.1 ? Check-in 1.1 In the proof, if and are finite automata where has states and has states Then how many states does have? (a) (b) (c) 11
• 12.
  Closure Properties continued Theorem:If are regular languages, so is (closure under ) Proof: Let recognize recognize Construct recognizing 𝑀2 𝑀1 should accept input if where accepts and accepts . 𝑀 𝑤 𝑥 𝑦 Doesn’t work: Where to split ? 12
• 13.
  Quick review oftoday 1. Introduction, outline, mechanics, expectations 2. Finite Automata, formal definition, 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
• 14.
  MIT OpenCourseWare https://ocw.mit.edu 18.404J Theoryof Computation Fall 2020 For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.