### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CS 215

UCR

GPA 3.88

### View Full Document

## 11

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 215 at University of California Riverside taught by Staff in Fall. Since its upload, it has received 11 views. For similar materials see /class/231746/cs-215-university-of-california-riverside in ComputerScienence at University of California Riverside.

## Reviews for THEORY OF COMPUTATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

The Emptiness Problem ETM 4 M j M is a TM and LM 4 Theorem Em is undecidable Proof a TM R deciding ETM gt a TM 3 deciding ATM S39s algorithm On input 1 F Check that 1 4 lt2 m If fail reject 1 N39 Construct a machine M such that for each input y e simulates M on m and accepts y if M has accepted Simulate R on Ml Accept 1 if R has accepted and reject 1 otherwise I 0 c5215 Lecture 9 9 1999 Mitsunon Ogihara Testing Whether a TM Accepts a Regular Language REGULARTM 4 M j M is a TM and LM is regular Theorem REG ULARTM is undecidable Proof a TM R deciding REGULARTM gt a TM 3 deciding A M S39s algorithm on input 11 1 Check that 1 4 XVI m If fail reject 11 2 Construct a machine M Let ml be two distinct symbols in the input alphabet E of M On input y a Accept 1 4 Mb for some n b Otherwise simulate M on m then accept y if and only if M on in has accepted c5215 Lecture 9 9 1999 Mitsunon Ogihara C8215 Lecture 9 9 1999 Mitsunori Ogihara The Halting Problem HALTTM 4 ltMm j M is a TM and halts on input m Theorem HA LTTM is undecidable Proof We can construct a machine 3 for ATM from a machine R for HALTTM On input 11 F Check that 4 Mgm If fail reject 11 Simulate R on m Reject 1 if R has rejected N39m39 M is guaranteed to halt on m simulate M on 1 Accept 1 if M has accepted and reject 1 otherwise I C8215 Lecture 9 c 1999 Mitsunori Ogihara Linear Bounded Automata A linear bounded automaton is a Turing machine wherein the head is not permitted to move beyond the region in which the input was written If the head attempts to move beyond the region it is kept at the same position Lemma Let M be an LBA with q states and with a tape alphabet of size For everyn 2 1 for every input of length there are precisely qnsquot possible configurations c5215 Lecture 9 9 1999 Mltsunon Oglhara 7 The Acceptance Problem for LBA ALBA 4 ltMm l M is a TM and accepts 1 when restricted to be an LBA Theorem A LBA is decidable Proof Let M be a TM with 1 states and 3 symbols in the tape alphabet and m be an input to M of length 7 By the previous lemma there are only gns configurations so if M on m accepts it should do so within qns steps So we have only to simulate M on m for qns steps I c5215 Lecture 9 9 1999 Mltsunon Oglhara 8 Proof cont d The machine M satisfies MM 4 MM 7 2 1 if M accepts 1 and 2 otherwise so M accepts 1 if and only if LM is not regular 3 Simulate R on Ml Accept 1 if R has rejected and reject 1 otherwise I C8215 Lecture 9 c 1999 Mltsunorl Oglhara 5 Testing Equivalence Between TMs 51M 4 ltMlMz l M and M are TMs and LM 4 LMZ Theorem Em is undecidable Proof a TM 1 deciding ETM gt a TM 3 deciding A M S39s algorithm on input F Check that 1 4 lt2 m If fail reject 1 Construct a machine M as in the previous proof Construct a machine Mg that accepts 2 Then LM 4 LMZ if and only if M does not accept m Simulate R on Mysz Accept 1 if R has rejected and reject 1 otherwise I N39 0 C8215 Lecture 9 c 1999 Mltsunorl Oglhara 5 The Equivalence Problem About CFG ALL 4 0 j G is a CFG and LGG 4 0 Theorem ALL is undecidable Proof For a sting 1 4 XMLm such that M is a Turing machine and m is an input to M let Ln be the set of all D1 D for which there exist 01 J such that 1 J are configurations of M 1 is the init39 l configuration of M on m I is an accepting configuration of M on m for every 2 g i g m i is the next configuration of OH and V39N39m39v39m39 forevery 1 g i g m Di 4 f is odd and Di 4 0 otherwise c5215 Lecture 9 9 1999 Mitsunon Ogihara Proof cont d Then Ln is empty if and only if M does not accept m 8017 4 2 fand only if M accepts 1 E is a CFL a TM 1 deciding ALLOW gt a TM 3 deciding ATM S39s algorithm on input 11 F Check that 4 XMLm If fa Construct a CFG G for reject N39m39 Simulate R on GM Accept 1 H has accepted G and reject 1 otherwise I c5215 Lecture 9 e 1999 Mitsunon Ogihara The Emptiness Problem About LBA ELBA 4 M j M is a TM and accepts no input viewed as an LBA Theorem ELM is undecidable Proof a TM 1 deciding ELBA gt a TM 3 deciding ATM For a sting 1 4 ltM m such that M is a Turing machine and m is an input to M let LE to be the set of all strings ofthe form 12 m such that 1 1 I are configurations of M 2 1 is the initial configuration of M on m 3 J is an accepting configuration of M on m and 4 forevery 1 g i g m1i1 is the next configuration of Oi C8215 Lecture 9 9 i999 Mltsunorl Oglhara Proof cont d Then Ln can be decided by an LBA Ln 71 0 if and only M accepts 1 3s algorithm on input 11 F Check that M m If fail reject 1 Construct a TM B that accepts Ln as an LBA No i Simulate R on B Reject 1 if R has accepted B and accept 1 otherwise I C8215 Lecture 9 e 1999 Mltsunorl Oglhara The Main Theorem The satisfiability problem is the problem of deciding whether a given input Boolean formula is satisfiable SA 1 4 f l f is a satisfiable Boolean formula Theorem SA 1 e P ifand only if 4 NP C8215 Lecture 13 2000 3 Polynomial Time Reductions Definition A function f is polynomial time computable if there exists a polynomial time TM that halts on each input r with only 1 on the tape Definition A language A is polynomial time mapping reducible to a language B write A gp B if A is mapping reducible to B via a polynomial time computable function C8215 Lecture 13 2000 4 NPCompleteness C8215 Lecture 13 2000 1 The PNP Problem ls P 4 NF Identify the most dif cult problems in NP NPcompleteness w A Boolean formula is a formula of propositional logic constructed from vari bles and Boolean operations A V a A Boolean formula is satisfiable ifthere exists some assignment to the variables that makes the formula evaluate to 1 Example f 4 T y V r E s satisfiable A satisfying assignment isr4 114141 4 r y is not satisfiable C8215 Lecture 13 2000 2 Proof of Theorem cont d Claim G has a Isaclique if and only if f is satis able jgtj Let S be a Isaclique of G Then S has a node from each triple so that the selected nodes do not interfere with each other as assignments jltj Let A be a satisfying assignment Select from each triple a literal that is satisfied by A to construct a set H S H4 Is and it is a clique The mapping is polynomial time computable I C8215 Lecture 13 2000 7 NPCompleteness Definition A language A is NPcomplete if A is in NP and every language in NP is polynomial time reducible to A Theorem A language A is NPcomplete and A e P then P 4 NP We may use the following to prove something is NPcomplete Theorem A language A is NPcomplete B e NP and A Q B then B is N Pcomplete C8215 Lecture 13 2000 8 3SAT A literal is a variable or its negation A clause is the disjunction of some literals eg gr V EV zrn A Boolean formula is in conjunctive normal form if 39t is the conjunction A of some clauses A 3CNFformula is a formula in CNFform in which each clause consists ofthree literals Theorem 38A 1 is polynomial time reducible to 71216 UE C8215Lecture132000 5 Proof of Theorem Given a formula 3 of Is threeliteral clauses construct a graph G 4 l1EwhereV 4 ltlj j 1 g 239 g ls1 g j g 3 and E 4 ltij lti j l 239 71 2quot and the jth literal in the 2th clause and the j th IIteral in the i th clause do not interfere with each other 71 X3 X4 39 39 quot7 2 V v W v The graph forthe formula f 4 392 V r VE Erj r2Er3 X c C8215 Lecture 13 2000 5 Encoding of Tableau Let C 4 QUI U and for each ij let aiilijj denote the jth element in row 239 For each 239j 1 g ij g M and s e 0 let r represent condition THIij 4 Encode Conditions 1 through 5 into Boolean formulas f through 35 and let r reduce to the conjunction ofthe five formulas There is a onetoone correspondence between the set of satisfying assignments and the set of all accepting tableaus C8215 Lecture 13 2000 11 Condition 1 squot Condition5 Accepting J Jimep Condition 3 if 12zm r 12jwj T12J u 1ltL n3 jgnk C8215 Lecture 13 2000 12 SAT is NPComplete Theorem SA 1 is NPcomplete Proof SA 1 e NP Consider a twotape NTM that on an input f of 7 variables guesses and writes an assignment A on Tape 2 using nondeterministic moves accepts if A 4 1 and rejects A 4 0 Such a machine decides SA 1 and can be polynomial time For the other part suppose A is in NP We show A 1 SA 1 Since A e NP there is some ls gt 0 and some M ime onetape NTM N such that LN 4 A We will show that a deterministic TM can construct a formula within a polynomial time bound for any given input to N describing accepting computations of N where that formula is satisfiable iffthere is such an accepting computation C8215 Lecture 13 2000 9 Tableau Let 1 be an input of length 7 Define a tableau for N on m to be an M gtlt M table whose entries are from U Q U P such that the columns 1 and M are all each row is a configuration of the first row is the initial configuration of N on r and V39N39m39v39 for each 239 2 g 239 g M the 2th row results from the 239 1st row applying one move of N A tableau is accepting if 5 the last row is an accepting configuration C8215 Lecture 13 2000 10 The Acceptance Problem for NFA Define AMA 4 Bgm l B is an NFA that accepts input string m Theorem AMA is decidable Proof Given an input 11 try to decode 1 nto an NFA B and a string 1 If successful then 1 Convert B to a DFA O W 2 Run the machine for AMA on Lm If the machine accepts then accept otherwise reject C8215 Lecture 7 9 1999 Mltsunon Oglhara 3 C8215 Lecture 7 9 1999 Mltsunorl Oglhara The Acceptance Problem for Regular Exp Decidable Problems About Regular Languages Define Alum 4 Etnn l R is a regular expression that produces m The Acceptance Problem for DFA Theorem Alum is decidable Define AMA 4 B m l B is a DFA that accepts input string m Proof Given an input 11 try to decode 1 into a regular expression 1 Here we assume a xed enCOdinQ SCheme for B and W and a string 1 If successful then Theorem AD is decidable 139 Convert R to a DFA 039 Proof A Turing machine can given an input 11 try to decode 1 into 2 Run the machine for ADM on 03 If the machine accepts then an NFA B and a string 1 If the decoding is successful then it can test accept39 otherwise reject whether B accepts 1 by simulating B on m I c5215 Lecture 7 e 1999 Mitsunon Ogihara 4 c5215 Lecture 7 9 1999 Mitsunori Ogihara The Acceptance Problem for CFG Define Acm 4 ltGm j G is a CFG that generates m Theorem Acm is decidable Proof Given an input 11 try to decode 1 into a CFG G and a string 1 If successful then F Convert G to an equivalent Chomsky normal form grammar G N39 List all derivations with 21 1 steps where n 4 mi 5 If any ofthe listed derivations generate m then accept otherwise reject c5215 Lecture 7 9 1999 Mitsunon Ogihara The Emptiness Problem for CFG Define EC 4 ltG j J is a CFG such that LG 4 0 Theorem EC is decidable Proof Given 1 first try to decode a grammar G out of it If pass then test the ab ty of generating terminal strings 1 Mark all the terminals 2 Repeat the following until no new symbols are marked Mark any variables A with a production A gt m such that all symbols in m are marked 3 Accept ifthe start symbol is marked reject otherwise c5215 Lecture 7 9 1999 Mitsunon Ogihara The Emptiness Problem for DFA Define EMA 4 A j A is a DFA that accepts no string Theorem EMA is decidable Proof Given an input 11 try to decode a DFA A out of 11 If successful then 1 Mark the start state of A 2 Repeat until no new states are marked Mark any unmarked state that has a transition from a marked state 5 Accept if no final state is marked reject otherwise C8215 Lecture 7 9 i999 Mitsunori Ogihara The Equivalence Problem for DFA Define EQDFA 4 AB j A and B are DFA that accept the same language Theorem EQDFA is decidable Proof Given a string 11 try to decode 1 into a pair of DFAs A and B If successful then construct a DFA G that accepts the symmetric difference of LA and LB LA m 3 U LA m LB and test the emptiness of LG I MA MB C8215 Lecture 7 e 1999 Mitsunori Ogihara

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.