# 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

• 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