BU CS 332 – Theory of Computation
Lecture 13:
• Mid-Semester Feedback • Enumerators
• Decidable Languages
• Countability
Reading: Sipser Ch 4.1
Mark Bun March 16, 2020
What aspects of the course help you learn best?
• Examples in class
• Reviewing past homeworks/exams in class
• Textbook
• Posting materials online
• Lecture, generally
• Office hours
• In-depth problem-solving in discussion section • Top Hat questions
• Piazza discussions / instructor response
3/16/2020 CS332 – Theory of Computation 2
What in the class so far has hindered your
learning?
• Pace of information transmission / workload
• Criteria for formality of proofs on homework and exams • Poor handwriting
• Questions in class not fully answered
• Lack of organization in discussion
• Broad concepts
• “Bureaucratic descriptions” • “All materials concluded”
3/16/2020 CS332 – Theory of Computation 3
What specific changes can we make to improve your learning?
• More examples
• Post solutions / other materials online • Discussion solutions
• More Top Hat questions
• Go slower
• More guidelines for how to solve each type of problem • Looser grading
• Midterm too long
• More detailed slides
3/16/2020 CS332 – Theory of Computation 4
Do you understand what is expected from you in this class?
• Reading the book before vs. after class
• Need to do every problem in the book to succeed?
• Lack of coordination between readings and lectures
• “I have to attend lectures, read the material in the book, do some practice problems and then attempt the homework”
• Exam grading critical over formatting vs. looser standards on homework
3/16/2020 CS332 – Theory of Computation 5
How can you improve your own learning?
• Read the book
• Solve more practice problems
• Review HW solutions
• Come to office hours
• Time management
• Open mind to more abstract ways of thinking
3/16/2020 CS332 – Theory of Computation 6
Enumerators
3/16/2020 CS332 – Theory of Computation 7
TMs are equivalent to…
• TMs with “stay put”
• TMs with 2-way infinite tapes
• Multi-tape TMs
• Nondeterministic TMs
• Random access TMs
• Enumerators
• Finite automata with access to an unbounded queue = 2- stack PDAs
• Primitive recursive functions
• Cellular automata
• “Turing-complete” programming languages (C, Python, …Java…)
3/16/2020 CS332 – Theory of Computation 8
Enumerators
Finite control
Work tape “Printer”
• Starts with two blank tapes
• Prints strings to printer
𝐿𝐿(𝐸𝐸) = {strings eventually printed by 𝐸𝐸}
• May never terminate (even if language is finite) • May print the same string many times
3/16/2020 CS332 – Theory of Computation 9
Enumerator Example
1. Initialize 𝑐𝑐 = 1
2. Repeat forever:
• Calculate 𝑠𝑠 = 𝑐𝑐2 (in binary) • Send 𝑠𝑠 to printer
• Increment 𝑐𝑐
What language does this enumerator enumerate?
3/16/2020 CS332 – Theory of Computation 10
Enumerable = Turing-Recognizable
Theorem: A language is Turing-recognizable ⇔ some enumerator enumerates it
⇐ Start with an enumerator 𝐸𝐸 for 𝐴𝐴 and give a TM
3/16/2020 CS332 – Theory of Computation 11
Enumerable = Turing-Recognizable
Theorem: A language is Turing-recognizable ⇔ some enumerator enumerates it
⇒ Start with a TM 𝑀𝑀 for 𝐴𝐴 and give an enumerator
3/16/2020 CS332 – Theory of Computation 12
Decidable Languages
3/16/2020 CS332 – Theory of Computation 13
1928 – The Entscheidungsproblem The “Decision Problem”
Is there an algorithm which takes as input a formula (in first- order logic) and decides whether it’s logically valid?
3/16/2020 CS332 – Theory of Computation 14
Design a TM which takes as input a DFA 𝐷𝐷 and a string 𝑤𝑤, and determines whether 𝐷𝐷 accepts 𝑤𝑤
Let 𝐷𝐷 = (𝑄𝑄, Σ, 𝛿𝛿, 𝑞𝑞 , 𝐹𝐹). List each component of the tuple
Questions about regular languages
How should the input to this TM be represented?
separated by ;
0
• Represent 𝑄𝑄 by ,-separated binary strings
• Represent Σ by ,-separated binary strings
• Represent 𝛿𝛿 ∶ 𝑄𝑄 × Σ → 𝑄𝑄 by a ,-separated list of triples (𝑝𝑝, 𝑎𝑎, 𝑞𝑞), …
Denotetheencodingof𝐷𝐷,𝑤𝑤by 𝐷𝐷,𝑤𝑤
3/16/2020 CS332 – Theory of Computation 15
Representation independence
Computability (i.e., decidability and recognizability) is not affected by the choice of encoding
Why? A TM can always convert between different encodings
For now, we can take to mean “any reasonable encoding”
3/16/2020 CS332 – Theory of Computation 16
A “universal” algorithm for recognizing regular
𝐴𝐴 = 𝐷𝐷,𝑤𝑤 DFA𝐷𝐷accepts𝑤𝑤} DFA
languages
Theorem: 𝐴𝐴DFA is decidable
Proof:Definea3-tapeTM𝑀𝑀oninput 𝐷𝐷,𝑤𝑤:
1. Check if 𝐷𝐷, 𝑤𝑤 is a valid encoding (reject if not)
2. 3.
Simulate 𝐷𝐷 on 𝑤𝑤, i.e.,
• Tape 2: Maintain 𝑤𝑤 and head location of 𝐷𝐷
• Tape 3: Maintain state of 𝐷𝐷, update according to 𝛿𝛿
Accept iff 𝐷𝐷 ends in an accept state
3/16/2020 CS332 – Theory of Computation 17
Other decidable languages
𝐴𝐴DFA = 𝐷𝐷, 𝑤𝑤 DFA 𝐷𝐷 accepts 𝑤𝑤} 𝐴𝐴NFA = 𝑁𝑁, 𝑤𝑤 NFA 𝑁𝑁 accepts 𝑤𝑤}
𝐴𝐴REX = 𝑅𝑅, 𝑤𝑤 regular expression 𝑅𝑅 generates 𝑤𝑤} 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤}
3/16/2020 CS332 – Theory of Computation 18
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is Turing-
recognizable
Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴
CFG
1. Enumerate all strings that can be generated from 𝐺𝐺
Oninput 𝐺𝐺,𝑤𝑤:
(i.e., all length-1 derivations, all length-2 derivations, …)
2. If any of these strings equal 𝑤𝑤, accept
3/16/2020 CS332 – Theory of Computation 19
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable
• Can have a rule 𝑆𝑆 → 𝜀𝜀
• Allremainingrulesoftheform𝐴𝐴→𝐵𝐵𝐵𝐵or𝐴𝐴→𝑎𝑎 • Cannot have 𝑆𝑆 on the RHS of any rule
Chomsky Normal Form for CFGs:
Lemma: Any CFG can be converted into an equivalent CFG in Chomsky Normal Form
Lemma: If 𝐺𝐺 is in Chomsky Normal Form, any nonempty string w that can be derived from 𝐺𝐺 has a derivation with at most2 𝑤𝑤 −1steps
3/16/2020 CS332 – Theory of Computation 20
CFG Generation
Theorem: 𝐴𝐴CFG = 𝐺𝐺, 𝑤𝑤 CFG 𝐺𝐺 generates 𝑤𝑤} is decidable Proof idea: Define a TM 𝑀𝑀 recognizing 𝐴𝐴CFG
Oninput 𝐺𝐺,𝑤𝑤:
1. Convert 𝐺𝐺 into Chomsky Normal Form 2.Enumerateallstringsderivablein≤2𝑤𝑤 −1steps 3. If any of these strings equal 𝑤𝑤, accept
3/16/2020 CS332 – Theory of Computation 21
Context Free Languages are Decidable
Theorem: Every CFL 𝐿𝐿 is decidable
Proof: Let 𝐺𝐺 be a CFG generating 𝐿𝐿. The following TM
decides 𝐿𝐿.
On input 𝑤𝑤:
1. Run the decider for 𝐴𝐴CFG on input 𝐺𝐺, 𝑤𝑤
2. Accept if the decider accepts; reject otherwise
3/16/2020 CS332 – Theory of Computation
22
Classes of Languages
recognizable
decidable context free
regular
3/16/2020 CS332 – Theory of Computation 23
More Examples
𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes the empty language} 𝐸𝐸CFG = 𝐺𝐺 𝐺𝐺 is a CFG that recognizes the empty language}
3/16/2020 CS332 – Theory of Computation 24
Decidability of 𝐸𝐸𝐷𝐷𝐷𝐷𝐷𝐷
Theorem: 𝐸𝐸DFA = 𝐷𝐷 𝐷𝐷 is a DFA that recognizes ∅} is
decidable
Proof: The following TM decides 𝐸𝐸
DFA
On input 𝐷𝐷 , where 𝐷𝐷 is a DFA with 𝑛𝑛 states:
1. 2.
Perform 𝑛𝑛 steps of breadth-first search on state diagram of 𝐷𝐷 to determine if an accept state is reachable from the start state
Accept if an accept state reachable; reject otherwise
3/16/2020 CS332 – Theory of Computation 25
3/16/2020 CS332 – Theory of Computation 26
Decidability of 𝐸𝐸𝐶𝐶𝐷𝐷𝐶𝐶
Theorem: 𝐸𝐸CFG = 𝐺𝐺 𝐺𝐺 is a CFG that recognizes ∅} is
decidable
Proof: The following TM decides 𝐸𝐸
On input 𝐺𝐺 , where 𝐺𝐺 is a CFG with 𝑛𝑛 states: 1. Mark all terminal symbols in 𝐺𝐺
CFG
2. 3.
Repeat until no new variable is marked: 1 2 𝑘𝑘 Markanyvariable𝐴𝐴where𝐺𝐺hasarule𝐴𝐴→𝑈𝑈 𝑈𝑈 …𝑈𝑈 and
every symbol 𝑈𝑈1, … , 𝑈𝑈𝑘𝑘 is marked
Accept if the start variable is unmarked; else reject
3/16/2020 CS332 – Theory of Computation 27
New Deciders from Old
𝐸𝐸𝑄𝑄DFA = ⟨𝐷𝐷1, 𝐷𝐷2⟩ 𝐷𝐷1, 𝐷𝐷2 are DFAs and 𝐿𝐿(𝐷𝐷1) = 𝐿𝐿(𝐷𝐷2)} Theorem: 𝐸𝐸𝑄𝑄DFA is decidable
Proof: The following TM decides 𝐸𝐸𝑄𝑄DFA
On input ⟨𝐷𝐷1, 𝐷𝐷2⟩ , where 𝐷𝐷1, 𝐷𝐷2 are DFAs:
1. Construct a DFA 𝐷𝐷 that recognizes the symmetric
difference 𝐿𝐿(𝐷𝐷1) △ 𝐿𝐿(𝐷𝐷2)
2. Run the decider for 𝐸𝐸DFA on 𝐷𝐷 and return its output 3/16/2020 CS332 – Theory of Computation 28
Symmetric Difference
𝐴𝐴△𝐵𝐵= 𝑤𝑤 𝑤𝑤 ∈𝐴𝐴or𝑤𝑤∈𝐵𝐵butnotboth}
3/16/2020 CS332 – Theory of Computation 29
Countability
3/16/2020 CS332 – Theory of Computation 30
Set Theory Review
A function 𝑓𝑓:𝐴𝐴 → 𝐵𝐵 is
• 1-to-1 (injective) if 𝑓𝑓 𝑎𝑎 ≠
𝑓𝑓 𝑎𝑎𝑎 forall𝑎𝑎 ≠𝑎𝑎𝑎
• onto (surjective) if for all 𝑏𝑏 ∈ 𝐵𝐵, there exists 𝑎𝑎 ∈ 𝐴𝐴 such that 𝑓𝑓𝑎𝑎=𝑏𝑏
• a correspondence (bijective) if it is 1-to-1 and onto, i.e., every 𝑏𝑏 ∈ 𝐵𝐵 has a unique 𝑎𝑎 ∈ 𝐴𝐴 with 𝑓𝑓𝑎𝑎=𝑏𝑏
3/16/2020 CS332 – Theory of Computation 31
How can we compare sizes of infinite sets?
Definition: Two sets have the same size if there is a bijection between them
A set is countable if
• it is a finite set, or
• it has the same size as N, the set of natural numbers
3/16/2020 CS332 – Theory of Computation 32
Examples of countable sets
•∅
• 0,1
• 0, 1, 2, … 8675309
• 𝐸𝐸 = {2,4,6,8,…}
• 𝑆𝑆𝑄𝑄𝑈𝑈𝐴𝐴𝑅𝑅𝐸𝐸𝑆𝑆 = 1,4,9,16,25,… • 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 = 1,2,4,8,16,32,…
𝐸𝐸 = 𝑆𝑆𝑄𝑄𝑈𝑈𝐴𝐴𝑅𝑅𝐸𝐸𝑆𝑆 = 𝑃𝑃𝑃𝑃𝑃𝑃𝑃 =|N|
3/16/2020 CS332 – Theory of Computation 33
How to show that N × N is countable? (1,1) (2,1) (3,1) (4,1) 5,1 …
(1,2) (2,2) (3,2) (4,2) (5,2) (1,3) (2,3) (3,3) (4,3) (5,3) (1,4) (2,4) (3,4) (4,4) (5,4) (1,5) (2,5) (3,5) (4,5) (5,5)
…
3/16/2020 CS332 – Theory of Computation
34