Download as PDF, PPTX
![Regular Expressions Regular operations. Let !, # be languages: - Union: ! ∪ # = & & ∈ ! or & ∈ #} - Concatenation: ! ∘ # = *+ * ∈ ! and + ∈ #} = !# - Star: !∗ = *- … */ each *0 ∈ ! for 1 ≥ 0} 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: - 0 ∪ 1 ∗ = Σ∗ gives all strings over Σ - Σ∗ 1 gives all strings that end with 1 - Σ∗ 11Σ∗ = all strings that contain 11 = : ;- Goal: Show finite automata equivalent to regular expressions 10](https://image.slidesharecdn.com/toc1-240310081949-b3491eb3/75/toc1-pdf-the-theory-of-computation-for-master-of-computer-applications-10-2048.jpg)
![&$ 1 &" , Closure Properties for Regular Languages Theorem: If !", !$ are regular languages, so is !" ∪ !$ (closure under ∪) Proof: Let &" = ()", Σ, +" , ," , -" ) recognize !" &$ = ()$, Σ, +$ , ,$ , -$ ) recognize !$ Construct & = (), Σ, +, ,0, -) recognizing !" ∪ !$ & should accept input 0 if either &" or &$ accept 0. Components of 2: Check-in 1.1 ) = )"×)$ In the proof, if &" and &$ are finite automata = ,", ,$ ," ∈ )" and ,$ ∈ )$} where &" has 8" states and &$ has 8$ states ,6 = (,", ,$) Then how many states does & have? (a) 8" + 8$ + ,, 1 , 7 = +" ,, 7 , +$ 1, 7 (b) 8" $ + 8$ $ - = -"×-$ NO! [gives intersection] (c) 8"×8$ - = -"×)$ ∪ )"×-$ Check-in 1.1 11](https://image.slidesharecdn.com/toc1-240310081949-b3491eb3/75/toc1-pdf-the-theory-of-computation-for-master-of-computer-applications-11-2048.jpg)
toc1.pdf the theory of computation for master of computer applications
- 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. 18.404 Course Outline ComputabilityTheory 1930s – 1950s - What is computable… or not? - Examples: program verification, mathematical truth - Models of Computation: Finite automata, Turing machines, … 2 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
- 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 Homework bi-weekly – 35% - Review concepts and more examples - More information to follow - Optional unless you are having difficulty Participation can raise low grades - Attend any recitation Midterm (15%) and Final exam (25%) - Open book and notes Text Check-in quizzes for credit – 25% - Introduction to the Theory of Computation - Distinct Live and Recorded versions Sipser, 3rd Edition US. (Other editions ok but - Complete either one for credit within 48 hours are missing some Exercises and Problems). - 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. Let’s begin: FiniteAutomata 0 1 !1 *1 *2 *3 0,1 1 0 Input: finite string Output: Accept or Reject States: *1 *2 *3 Computation process: Begin at start state, 1 Transitions: read input symbols, follow corresponding transitions, Accept if end with accept state, Reject if not. Start state: Examples: 01101 → Accept Accept states: 00101 → Reject !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
- 7. Finite Automata –Formal Definition Defn: A finite automaton ! is a 5-tuple (#, Σ, &, '0, )) # finite set of states Σ finite set of alphabet symbols Example: & transition function &: #×Σ → # a & (', .) = 0 means ' 0 0 '0 start state !1 1 0,1 1 ) set of accept states '1 '2 '3 0 !1 = (#, Σ, &, '1, )) & = 0 1 # = {'1, '2, '3} '1 '1 '2 Σ = {0, 1} '2 '1 '3 ) = {'3} '3 '3 '3 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 Recognizing languages - The empty language ø is the set with no strings - :(#) = {$| # accepts $} - :(#) is the language of # Defn: # accepts string $ = $1$2 … $) each $* + Σ - # recognizes :(#) if there is a sequence of states ,0, ,1, ,2, , … , ,) + / where: - ,0 = 00 - ,* = 1(,345, $*) for 1 ≤ * ≤ ) Defn: A language is regular if some - ,) + 8 finite automaton recognizes it. 8
- 9. Regular Languages –Examples 0 1 "1 81 82 83 0,1 1 0 More examples: ! "# = {&| & contains substring 11} = 5 Let 6 = & & has an even number of 1s} Therefore 5 is regular 6 is regular (make automaton for practice). Let 7 = & & has equal numbers of 0s and 1s} 7 is not regular (we will prove). Goal: Understand the regular languages 9
- 10. Regular Expressions Regular operations.Let !, # be languages: - Union: ! ∪ # = & & ∈ ! or & ∈ #} - Concatenation: ! ∘ # = *+ * ∈ ! and + ∈ #} = !# - Star: !∗ = *- … */ each *0 ∈ ! for 1 ≥ 0} 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: - 0 ∪ 1 ∗ = Σ∗ gives all strings over Σ - Σ∗ 1 gives all strings that end with 1 - Σ∗ 11Σ∗ = all strings that contain 11 = : ;- Goal: Show finite automata equivalent to regular expressions 10
- 11. &$ 1 &" , Closure Properties forRegular Languages Theorem: If !", !$ are regular languages, so is !" ∪ !$ (closure under ∪) Proof: Let &" = ()", Σ, +" , ," , -" ) recognize !" &$ = ()$, Σ, +$ , ,$ , -$ ) recognize !$ Construct & = (), Σ, +, ,0, -) recognizing !" ∪ !$ & should accept input 0 if either &" or &$ accept 0. Components of 2: Check-in 1.1 ) = )"×)$ In the proof, if &" and &$ are finite automata = ,", ,$ ," ∈ )" and ,$ ∈ )$} where &" has 8" states and &$ has 8$ states ,6 = (,", ,$) Then how many states does & have? (a) 8" + 8$ + ,, 1 , 7 = +" ,, 7 , +$ 1, 7 (b) 8" $ + 8$ $ - = -"×-$ NO! [gives intersection] (c) 8"×8$ - = -"×)$ ∪ )"×-$ Check-in 1.1 11
- 12. Closure Properties continued Theorem:If !", !$ are regular languages, so is !"!$ (closure under ∘) Proof: Let &" = ()", Σ, +" , ," , -" ) recognize !" &$ = ()$, Σ, +$ , ,$ , -$ ) recognize !$ Construct & = (), Σ, +, ,0, -) recognizing !"!$ & should accept input 0 if 0 = 12 where &" accepts 1 and &$ accepts 2. &$ &" & 0 1 2 Doesn’t work: Where to split 0? 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 /18.4041J / 6.840J Theory of Computation Fall 2020 For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms.