### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Introduction to Theoretical Computer Science CS 390

ODU

GPA 3.7

### View Full Document

## 23

## 0

## Popular in Course

## Popular in ComputerScienence

This 11 page Class Notes was uploaded by Armani Kunde on Monday September 28, 2015. The Class Notes belongs to CS 390 at Old Dominion University taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/215316/cs-390-old-dominion-university in ComputerScienence at Old Dominion University.

## Reviews for Introduction to Theoretical Computer Science

### 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: 09/28/15

Lecture We have discussed unreachable states in FAs and uneXecutable code in programs in the past Let us look at a theorem that allows one to delete such states and code Page 1 l7 problem 3 29 in your text is in fact this theorem De nition Let M Q E qo A 5 be and FA For elements p and q of Q q is reachable om p if there is a string X over 2 such that 8pX q Theorem Let M1 be the FA obtained from M by deleting any states from M that are not reachable from qo and any transitions to or from such states Then M and M1 accept the same languages Proof Note that M1 Q1 2 ql A1 81 where Q1 is the subset ofreachable states in Q and we choose q1 qo A1 A0 intersected with Q1 and 51 to be the restriction 5 to input states that are in Q1 Let L and L1 be the languages accepted by M and M1 respectively We must prove these two sets are equal For any string X in L1 51 ql X is in A1 by definition of language acceptance But 51 ql X 5 qo X Since A1 is a subset owae know that 5 qo X is in A and hence X is in L That was half of the proof For any string X in L 5 qo X is in A by definition of language acceptance Certainly 5 qo X is in A1 since it is reachable Clearly every state on the path from qo to 5 qo X is in Q1 However just to be safe let us prove this by induction on the length X of string X that every state on this path is in Q1 Basis If the X 0 then X is the empty string A and the entire path consists of the stage qo Which is the initial state in Q1 IH Statement is true of all X of length n for some n gt 0 IS Consider an X of length nl Then X ya for some string y of length n and some character a in the alphabet 2 Thus 5 qo ya 5 5 qo y a by definition of 5 By 1H every state on the path from qo to 5 qo y is in A1 The final state 5 qo ya is reachable by definition Therefore by induction it is true for all strings y of length n1 that every state on the path from qo to 5 qo y is reachable Note The above theorem allows us to ignore unreachable states and to use greedy techniques when applying Theorem 34 Theorem 41 and Theorem 42 As you recall in applying Theorem 34 we began with our starting state and added only those states that were absolutely necessary to have an FA instead of including all of the states in Q1 X Q2 described by the theorem Theorem 41 For any NFAM Q Eqo 146 accepting a language L g 2 there is anFA M1 Q1 3 ql A1 81 that also accepts Li Proof MI is de ned as follows Q1 29 q qu forq e Ql anda 6 251014 U3ra y 69 i A1inQilan9 m w The last de nition is the right one because a string x should be accepted by w M if Starting in go the set of states in which M might end up as a result of t i processing x contains at least one element of A I The fact that M accepts the same language as M follows from the fact 2 t that foranyx e 2 81qi 2 540 x which we now prove using structural induction on x Note that the functions 8 and 8 are de ned in different ways 8 in De nition 42b since M is an NFA and 6 in De nition 33 since M1 is an FA Ifx A 5811 I 5311 A q1 by de nition of 6 qol by de nition of q1 6 q03 A by de nition of 8 57110 x The induction hypothesis is that x is a string satisfying 8fqx 8qo x and we wish to prove that for any a e 3 51q1 xa 8qo xa 5fqis m 515Tq1x a by de nition afar 818 qo x a by the induction hypothesis U 6r a by de nition of 8 rerun 8 qo xa by de nition of 8 That M and M1 recognize the same language is now easy to see A string x is accepted by M1 if8fq1 x e A we can now say that this is true if and only if 5qo x e A and using the de nition of A I we conclude that this is true if and only if 8quot go x H A Q In other words it is accepted by M1 if and only if x is accepted by M on 44 A Nondeierml slic Finite Automaton with A Tran A nondeterministic nite automaton with A u39ansitions abbreviated NFA A is a 5 luple Q Ll01115 where Q and Z are nite sets qo E Q A g Q and 5Qx2UA gt29 De nition 46 ACIosure of a Set of States Let M Q 2 In A 3 be an NFA A and let S be any subset of Q The Aclosure of S is the set S de ned as follows 1 Every element of S is an element of HS 2 For any I E INS eveiy ele11enlof5q A is in A0quot 3 No other elements of Q in NS Figure 49 l The NFAA for Example 46 Calculate ApuV De niiion 45b Recursive Definition of 5 hr an NF i Let M Q 210 A 6 be an NFA A The extended transition function 6 2 Q x 2 gt 20 is de ned as follows I Foranyq E QB39q A MM 2 Faranyq e Qnr E 239 anda E 2 51 y A U Mm wimpy A string x is accepted by M if 6140 r n A g M The language recognized by M is the set UM of all swings accepted by M Figure 49 I The NFAA for Example 46 Calculate 5q0 101 Theorom 42 IfL g E isalanguagethatis acceptedby theNFA A M Q 3 go A 15 then thereis an NFA M Q1 E 41 As that also accepts L Proof In the proof of Theorem 41 we started with an NFA and removed all traces of nondeterminjsm by changing our notion of state A Atransition is a type of nondetemxinism for example if the transitions in M include 0 A p gtq gtr then from state 7 the input symbol 0 allows us to go to either q or r Since M I is still allowed to be nondetemtinistic we can eliminate the A transition without changing the states by simply adding the transition from p to r on input 0 This approach will work in general We can use the same state set Q and the same initial state in M I What we must do is to de ne the transition function 5 1 so that if M allows us to move from p to q using certain symbols together with A transitions then M I will allow us to move from p toq using those symbols without the A transitions Essentially we have the solution already as a result of the de nition of 8quot for the NFA A M De nition 45b For a state q and an input symbol a 5q a5quotqua A U Bra rei thU A U 5r a rsAl lql Remember what this means UEAlq5r a is the set of states that can be reached from 1 using the input symbol a but possibly also A transitions beforehand The Aclosure of this set is the set of states that can be reached from qt using the input symbol a but allowing Atransitions both before and after This is exactly what we want 50 0 to be in order to incorporate into our NFA transition function the nondeterminism that arises front the possibility of Atransitions Finally there is a slight change that may be needed in specifying the accepting states of M1 If the initial state qo of M is not an accepting state but it is possible to get from qo to an accepting state using only Atransitions then go must be made an accepting state in M l otherwise 6 q0 A which is qu because M1 is an NFA will not intersect A To summarize we have decided that M1 will be the NFA Q E 10 Al 81 where for any I e Q anda e Z 5it1t1 5qa and A AUlchl ifAillol A VlinM A otherwise The point ofour de nition ofle is that we want 5fq x to be the set of states that M can reach from 1 using the symbols of the string x together with Atransitions In other words we want 8TH t39 539q x This formula may not be correct when x A because M1 is an NFA 871 A q whereas 6 14 A may contain additional slates and that is the reason for our de nition of A above We now show however that for any nonnull string the formula is true The proof is by structural induction on x For the basis step we consider x a E 3 In this case 8qx 5qa by de nition of 51 and 61q a 8fq a simply because M is an NFA see Example 42 and Exercise 43 In the induction step we assume that lyl z i and that 8fq y 5q y for any 1 e Q We want to show that for a e 22 5fq ya 6q ya We have STU ya U 6 r i by De nition 42b re qq U 6100 by the induction hypothesis rea39tqy U mm byde nitionofsl rs my II A U 5mm by De nition45b MSW3 PEMI The A closure operator has the property that the union of Aclosures is the Aclosure of the union Exercise 440 We may therefore write the last set as A U U Mp 0 re 39tqty peAlr However it follows from the de nition of A ciosure and the fact that 6 q y is a Aclosure that forever r E 5q y Mr E 5quotq y there fore the two separate unions are unnecessary and the formula reduces to A U 602 a rerS39lq yl which is the de nition of 511 ya The induction is complete Now it is not hard to show that M I recognizes L the language recog nized by M First we consider the case when Aqg n A a in M Then the null string is accepted by neither M nor M1 For any other string x we have shown that 81qn x 6q0 x and we know that the accepting states of M and M are the same Therefore x is accepted by M if and only if it is accepted by M In the other case when Aqo H A 0 we have de ned A to be A U go This time A is accepted by both M and M For any other x again we have 81 40 x 5qo x If this set contains a state in A then both M and M1 accept x If not the only way x could be accepted by one of the two machines but not the other would be for 5 go x to contain get It would then intersect A but not A However this cannot happen either By de nition 8 q0 x is the Aclosure of a set If 8qo x contained qo it would have to contain every element of Aqg and therefore since Aqu n A a w it would have to contain an element of A In either case we may conclude that M and M I accept exactly the same strings and the proof is complete Theorem 43 For any alphabet E and any language L C 3quot these three statements are equivalent 1 L can be recognized by an FA 2 L can be recognized by an NFA 3 L can be recognized by an NFAA

### 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 made $350 in just two days after posting my first study guide."

#### "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."

#### "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.