CS代考计算机代写 Java Context Free Languages python algorithm BU CS 332 – Theory of Computation

BU CS 332 – Theory of Computation
Lecture 13:
• Mid‐Semester Feedback • Enumerators
• Decidable Languages
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
2.
Repeat forever:
• Calculate 􏶊 (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

Questions about regular languages
Design a TM which takes as input a DFA and a string , and determines whether accepts
How should the input to this TM be represented?
Let
separated by ;
􏵹 . List each component of the tuple
• Represent
by ,‐separated binary strings by ,‐separated binary strings
• Represent
• Represent ,…
by a ,‐separated list of triples
Denote the encoding of 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 languages
􏶟􏶘􏶠
Theorem: 􏶟􏶘􏶠 is decidable
Proof: Define a 3‐tape TM on input
1. 2.
Check if is a valid encoding (reject if not)
3.
Accept iff ends in an accept state
Simulate on , i.e.,
• Tape 2: Maintain 𝑤 and head location of 𝐷
• Tape 3: Maintain state of 𝐷, update according to 𝛿
3/16/2020 CS332 ‐ Theory of Computation 17

Other decidable languages
􏶟􏶘􏶠 􏷄􏶘􏶠
􏷅􏷆􏷇 􏶗􏶘􏶙
3/16/2020 CS332 ‐ Theory of Computation 18

CFG Generation
Theorem: 􏶗􏶘􏶙 recognizable
is Turing‐
Proof idea: Define a TM
recognizing
􏶗􏶘􏶙
On input :
1. Enumerate all strings that can be generated from
(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: 􏶗􏶘􏶙 is decidable
Chomsky Normal Form for CFGs:
• Canhavearule𝑆 → 𝜀
• Allremainingrulesoftheform𝐴→𝐵𝐶or𝐴→𝑎 • Cannot have 𝑆 on the RHS of any rule
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 most steps
3/16/2020
CS332 ‐ Theory of Computation 20

CFG Generation
Theorem: 􏶗􏶘􏶙
Proof idea: Define a TM recognizing
is decidable
On input :
1. Convert into Chomsky Normal Form 2. Enumerate all strings derivable in
3. If any of these strings equal , accept
steps
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 􏶗􏶘􏶙 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
􏶟􏶘􏶠
􏶗􏶘􏶙
3/16/2020 CS332 ‐ Theory of Computation 24

Decidability of
Theorem: 􏶟􏶘􏶠 decidable
is
Proof: The following TM decides
On input , where is a DFA with
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
􏶟􏶘􏶠
states:

3/16/2020 CS332 ‐ Theory of Computation 26

Decidability of
Theorem: 􏶗􏶘􏶙 decidable
is
Proof: The following TM decides
On input , where is a CFG with
1. 2.
states: Repeat until no new variable is marked:
3.
every symbol 𝑈􏵶, … , 𝑈􏶇 is marked
Accept if the start variable is unmarked; else reject
Mark all terminal symbols in
Mark any variable 𝐴 where 𝐺 has a rule 𝐴 → 𝑈􏵶𝑈􏶊 …𝑈􏶇 and
3/16/2020 CS332 ‐ Theory of Computation 27
􏶗􏶘􏶙

New Deciders from Old
􏶟􏶘􏶠􏵶􏶊􏵶􏶊 􏵶􏶊 Theorem: 􏶟􏶘􏶠 is decidable
Proof: The following TM decides
On input 􏵶 􏶊 , where 􏵶 􏶊 are DFAs:
1. Construct a DFA that recognizes the symmetric
difference
􏵶􏶊
2. Run the decider for 􏶟􏶘􏶠 on and return its output 3/16/2020 CS332 ‐ Theory of Computation 28
􏶟􏶘􏶠

Symmetric Difference
3/16/2020 CS332 ‐ Theory of Computation 29