Introduction to Theory of Computation: Course Overview and Mechanics
Explore the fundamentals of computability and complexity theories with a focus on finite automata, Turing machines, P versus NP problem, and more. Dive into the role of theory in computer science, collaboration policies, and course expectations. Get ready for a comprehensive journey into the world of computation theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
18.404/6.840 Intro to the Theory of Computation Instructor: Mike Sipser TAs: - Fadi Atieh, Damian Barabonkov, - Alex Dimitrakakis, Thomas Xiong, - Abbas Zeitoun, and Emily Liu 1
18.404 Course Outline Computability Theory 1930s 1950s - What is computable or not? - Examples: program verification, mathematical truth Complexity Theory 1960s present - What is computable in practice? - Models of Computation: Finite automata, Turing machines, - Example: factoring problem - P versus NP problem - Measures of complexity: Time and Space - Models: Probabilistic and Interactive computation 2
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 Homework bi-weekly 35% - More information to follow Midterm (15%) and Final exam (25%) - Open book and notes Check-in quizzes for credit 25% Text - - - - Distinct Live and Recorded versions Complete either one for credit within 48 hours Initially ungraded; full credit for participation Introduction to the Theory of Computation Sipser, 3rd Edition US. (Other editions ok but are missing some Exercises and Problems). 3
Course Expectations Prerequisites Prior substantial experience 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
Role of Theory in Computer Science 1. Applications 2. Basic Research 3. Connections to other fields 4. What is the nature of computation? 5
Lets begin: Finite Automata 0 1 ?1 0,1 1 ?3 ?1 ?2 0 Input: finite string Output: Accept or Reject States: ?1 ?2 ?3 Computation process: Begin at start state, read input symbols, follow corresponding transitions, Accept if end with accept state, Reject if not. 1 Transitions: Start state: Examples:01101 Accept 00101 Reject Accept states: ?1 accepts exactly those strings in ? where ? = {?| ? contains substring 11}. Say that ? is the language of ?1 and that ?1 recognizes ? and that ? = ?(?1). 6
Finite Automata Formal Definition Defn: A finite automaton ? is a 5-tuple (?, ,?,?0,?) ? finite set of states finite set of alphabet symbols Example: Example: ? transition function ?: ? ? a ? ? (?, ?) = ? means ? 0 ?1 ?0 start state 1 0,1 1 ?1 ?2 ?3 ? set of accept states 0 ?1 = (?, ,?,?1,?) ? = 0 1 ? = {?1,?2,?3} ?1 ?2 ?3 ?1 ?1 ?3 ?2 ?3 ?3 = {0,1} ? = {?3} 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 Recognizing languages - ?(?) = {?| ? accepts ?} - ?(?) is the language of ? - ? recognizes ?(?) The empty language is the set with no strings - Defn: ? accepts string ? = ?1?2 ??each ?? ? if there is a sequence of states ?0,?1,?2,, ,?? ? ? where: - ?0 = ?0 - ?? = ?(?? 1,??) for 1 ? ? - ?? ? ? Defn: A language is regular if some finite automaton recognizes it. 8
Regular Languages Examples 0 ?1 1 0,1 1 ?3 ?1 ?2 0 More examples: More examples: ? ?1 = {?| ? contains substring 11} = ? Let ? = ? ? has an even number of 1s} ? is regular (make automaton for practice). Therefore ? is regular Let ? = ? ? has equal numbers of 0s and 1s} ? is not regular (we will prove). Goal: Understand the regular languages 9
Regular Expressions Regular operations. Regular operations. Let ?,? be languages: ? ? = ? ? ? or ? ?} - Union Union: : - Concatenation: Concatenation: ? ? = ?? ? ? and ? ?} = ?? ? = ?1 ??each ?? ? for ? 0} Note: Note: ? always - Star: Star: Regular expressions Regular expressions Built from , members , , [Atomic] - By using , , [Composite] - Example. Example. Let ? = {good, bad} and ? = {boy, girl}. - ? ? = {good, bad, boy, girl} Examples: Examples: 0 1 = gives all strings over - 1 gives all strings that end with 1 - 11 = all strings that contain 11 = ? ?1 - ? ? = ?? = {goodboy, goodgirl, badboy, badgirl} - - ? = { , good, bad, goodgood, goodbad, badgood, badbad, goodgoodgood, goodgoodbad, } Goal: Show finite automata equivalent to regular expressions 10
Closure Properties for Regular Languages Theorem: Theorem: If ?1, ?2are regular languages, so is ?1 ?2 (closure under ) Proof: Proof: Let ?1= (?1, , ?1, ?1, ?1)recognize?1 ?2= (?2, , ?2, ?2, ?2)recognize?2 Construct ? = (?, , ?, ?0, ?) recognizing?1 ?2 ?should accept input ? if either ?1 or ?2 accept ?. Components of Components of ?: : Check-in 1.1 ?1 ? ? = ?1 ?2 = ? In the proof, if ?1 and ?2 are finite automata where ?1 has ?1 states and ?2 has ?2 states Then how many states does ? have? (a) ?1+ ?2 (b) ?1 (c) ?1 ?2 ?1,?2 ?1 ?1and ?2 ?2} ?,? ? ?0= (?1,?2) ? ?,? ,? = ?1?,? ,?2?,? NO! NO! [gives intersection] ?2 2+ ?2 2 ? = ?1 ?2 [gives intersection] ? ? = ?1 ?2 ?1 ?2 Check-in 1.1 11
Closure Properties continued Theorem: Theorem: If ?1, ?2are regular languages, so is ?1?2 (closure under ) Proof: Proof: Let ?1= (?1, , ?1, ?1, ?1)recognize?1 ?2= (?2, , ?2, ?2, ?2)recognize?2 Construct ? = (?, , ?, ?0, ?) recognizing?1?2 ?2 ?1 ? should accept input ? if ? = ?? where ?1 accepts ? and ?2 accepts ?. ? ? ? ? Doesn t work: Where to split ?? 12
Quick review of today 1. 1. Introduction, outline, mechanics, expectations Introduction, outline, mechanics, expectations 2. 2. Finite Automata, formal definition, regular languages Finite Automata, formal definition, regular languages 3. 3. Regular Operations and Regular Expressions Regular Operations and Regular Expressions 4. 4. Proved: Class of regular languages is closed under Proved: Class of regular languages is closed under 5. 5. Started: Closure under Started: Closure under , to be continued , 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.
