### Create a StudySoup account

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

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CSCE 551

GPA 3.61

### View Full Document

## 47

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 149 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 551 at University of South Carolina - Columbia taught by M. Alekseyev in Fall. Since its upload, it has received 47 views. For similar materials see /class/229570/csce-551-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## 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/26/15

Theory of Computation Lecture 4 Nondeterministic Finite Automata Max Alekseyev University of South Carolina January 22 2009 Lectu re Outline Nondeterminism Nondeterministic Finite Automata NFA Computation Equivalence of DFAs and NFAs Regular Languages revisited Clean NFA Nondeterminism In a DFA the next state is completely determined by the current state and the symbol being scanned according to the transition function 6 In a nondeterministic finite automaton there may be a choice of several states to transition into at each step and we may decide not to advance the read head The machine accepts the input ifF there is some series of choices that can lead to an accepting state having read the entire input Transition diagram may have any number of edges with the same label leaving the same state There can also be c edges meaning make the transition without reading the symbol or advancing the read head Nondeterministic Finite Automata Given an alphabet X we define XS X U a which is the set of all strings over X of length 0 or 1 Definition A nondeterministic finite automaton NFA is a 5 tuple Q7 X7 6 qo F where gt Q is a finite set the set of states gt X is a finite set the alphabet gt 6 Q x XS H 73Q is the transition function gt qo E Q is the start state and gt F Q Q is the set of accepting states NFA Example Example of an NFA that recognizes the language of strings over 3 b that start with b and contain either 333 or abbaa as a substring ogeoe ab 9 U Q There is no outgoing edge labeled a from the node 0 What does that mean N FA Computation Notice that 6q7 a is now a set of states instead ofjust a single state It is the set of possible successor states of q reading a In particular 6776 is also defined to be a set of states This is the set of possible successors to q via an c transition Such a transition when taken does not advance the read head Given an NFA M and an input string W there may now be many possible computations or computation paths of M on W We say that M accepts W ifF at least one of these computation paths ends in a final state after reading all of W lnformally M accepts if there is a correct set of transition guesses that leads to an accepting state and reads the entire input NFA Computation Definition Let M Q7X767 qo7 F be an NFA and let W E X be a string A complete computation of M on input W is a pair of tuples 5075my17ym where gt s Qforall0 i m gtyiengorall1 i m W Y1 me gt so qo and gt s E 6s1y for all 1 g i g m The complete computation above is accepting ifF sm 6 F otherwise it is rejecting We say that M accepts W if there exists some accepting complete computation of M on W A complete computation represents a legal path through the NFA while reading the entire input e transitions correspond to steps where y 6 Q What can Vou saV about lWl and m DFA vs NFA As with DFAs before we define the language LM recognized by NFA M to be the set of all input strings accepted by M We say that two automata N FAs or DFAs are equivalent ifF they recognize the same language Our goal is to show that DFAs and NFAs are equally powerful models of computation that is they recognize the same class of languages namely the regular languages We show this in two steps 1 For every DFA there is an equivalent NFA 2 For every NFA there is an equivalent DFA From DFA to NFA This direction is obvious Q Why From DFA to NFA This direction is obvious For any DFA make an equivalent NFA with the same transition diagram Each 6q7 a is a singleton for a E X and 6q7 e 0 More formally if M QX6 qo F is a DFA define the NFA N Q7 ZN qo F where gt 6 qa 6qa for all q E Q and a E X and gt 6 q6 0 for all q E Q It39s easy to see that LN LM ie that N is equivalent to M From NFA to DFA Theorem For every NFA there is an equivalent DFA We give a sketch of a proof which includes the construction of the equivalent DFA but does not verify that it is correct The idea of the proof is that as we simulate a given NFA we keep track of the set of all states we could be in after reading each successive symbol of the input From NFA to DFA the states For a given NFA M we will construct an equivalent DFA N If 5 is the set of all states of M we could possibly get to by reading the input up to but not including a symbol a then the set 5 of states of M that we could possibly be in after reading a only depends on 5 and a and can be computed from the transition diagram of M We make each possible set 5 of states in M a single state of the DFA N and the transitions of N correspond to shifting the set of possible states of M upon reading each symbol For example the transition 5 i 5 would be a transition in N There are only finitely many subsets of the states of M so N is really a deterministic finite automaton From NFA to DFA the start state and e transitions Note that M may have e transitions that need to be taken into account So for a state 5 in N and a E X to define a transition 5 i 5 we first follow any a transitions from states in 5 and then follow any e transitions thereafter possibly several in a row Q Should we also follow any e transitions before the a transitions From NFA to DFA the start state and e transitions Note that M may have c transitions that need to be taken into account So for a state 5 in N and a E X to define a transition 5 i 5 we first follow any a transitions from states in 5 and then follow any c transitions thereafter possibly several in a row The start state of N corresponds to the set of states of M that one could possibly be in before reading any input symbols This is exactly the set of states reachable from the start state of M via c transitions only A set 5 of states of M constitutes an accepting state of N iff it includes at least one accepting state of M ie the computation could possibly be in a final state of M From NFA to DFA E closure Suppose that the given NFA M Q7 X 6 L707 F For any set 5 Q Q of states of M we define the c closure of 5 denoted E to be the set of states reachable from 5 via zero or more c transitions in a row Formally for i 2 O we define E inductively to be the set of states reachable from 5 via exactly 139 many c transitions so that E0 5 and for all i 2 0 Ei1sr 6 Q l Ba 6 Ei5r e mail U 6mg 1655 This lets us define 55 U Ei57 1 20 namely the set of all states reachable from 5 via zero or more c transitions Note that E is closed under c transitions ie there are no c transitions from inside E to outside E From NFA to DFA Formal Construction Given an NFA M QX6 qo F an equivalent DFA can be constructed as N PM7 LA 50 where gt 73Q is the powerset of Q gt 50 Eq0 the set of states reachable from qo via c transitions gt f QlSOFy wthesetofsetsofstatesofM which contain final states of M and gt for every 5 Q Q and a E X Aa E U 6q 51 165 From the above definition every state of N that is reachable from the start state 50 is closed under c transitions so there is no need to follow c transitions before a transitions in the definition of A Constructing an equivalent DFA When an NFA is converted to an equivalent DFA often not all the possible sets of states of the NFA are used so not all the DFA states are reachable from the start state and they can be eliminated eg any state sets which are not closed under c transitions As a practical matter instead of including all possible subsets of states of the NFA it39s better to grow the DFA states from the start state by following transitions You will usually wind up with a lot fewer DFA states this way To construct the equivalent DFA we build its states one by one starting with its start state then following transitions Whenever we encounter a new set of states of the NFA we add it as a new state to the DFA From NFA to DFA an Algorithm Input NFA M Q7X767qo7 F Output equivalent DFA N Q7X7A7507f Set A 0 no transitions yet Set f 0 no final states yet Set 50 Eq0 Set Q 50 While there is an unmarked S E Q do For every 3 E X do Let T be the set of states reachable from states in 5 via an a transition followed by any number of s transitions Add the transition A7 a T to A If T Q then Q Q U T If T F7 0thenffUT End for Mark S as processed End while Return N OS X Al Snurl Algorithm Execution Let39s apply this algorithm to the NFA that recognizes the language of strings over 3 b that start with b and contain either 333 or abbaa as a substring babbaa W v ab The start state of the DFA is 0 EO Compute the transitions from 50 First the a transition there is nothing reachable from state 0 following a so the new state of the DFA is Q and we have A07 a 0 which is a new state so we call it 51 and add it to Q So we now have Q 5051 where 51 Q and the diagram looks like this 9 Algorithm Execution ogeoe ab 3 U Starting back at state 0 and following b the only state we can reach is 1 so we have a new state 52 1 and set A07 b 2 How about transitions from 1 51 has no states of the NFA so we cannot get anywhere from 51 following any symbol Thus A517 a A1 b 0 17 and we should add two self loops from 1 to itself The diagram becomes 9 a b b 9 0 and 51 are both processed at this point Algorithm Execution Now we focus on 52 Following a from state 1 of the NFA we can get to states 1 and 2 then following the c transition from 2 we can get to 4 Thus we have a new state 53 17 27 4 A2 a Following b from state 1 we can only get back to state 1 so A2 b 1 2 and we put a self loop 2 3 52 Here39s the new diagram 31 Algorithm Execution Now we follow transitions from 53 For the a transition the NFA has transitions 1 i 1 13gt 2 and 4 i 5 In addition we can get from 2 to 4 again by following 8 So we have a new state 54 1245 A3a For the b transition the NFA has 1 g 1 and 2 g 3 with no additional s moves So we have a new state 55 17 3 A3 b and the diagram for the DFA is now a b 999 O b b Algorithm Execution Following a from 4 the NFA has a transitions to states 1 2 5 and 6 with an e move to 4 So we get a new state 56 12457 6 A4a Since 56 O F 6 7 0 6 is our first final state Following b from states in 54 we can reach states land 3 and no others and there are no additional e transitions possible Since 55 13 we have A47 b 55 M b Algorithm Execution 03909 a b a U We continue this way until each state of the DFA has a single outgoing edge for every alphabet symbol The complete DFA looks like this Note that this is not an optimal solution For example all the accepting states can be coalesced into a single accepting state Regular Languages revisited Corollary A language is regular iff it is recognized by some NFA Let X be an alphabet X and A7 B be two languages A7 B Q X Previously we have already defined operations A U B A O B and AR for an integer k 2 0 Further useful operations gt A X A the complement of A in X This is the set of all strings over X that are not in A gt A o B xy l X E A and y E B the set of all concatenations of a string in A followed by a string in B This operation on languages is associative gt Aquot A0 U A1 U A2 U This is called the Kleene closure or Kleene star of A All these operations preserve regularity ie if A and B are regular then so are all the resulting languages above Q What is a DFA for A given a DFA for A Clean NFA This is not in the book The notion of a clean NFA pops up on several occasions Definition Let M be an NFA We say that M is clean iff gt M has exactly one final state which is distinct from the start state gt M has no transitions into its start state even self loops and gt M has no transitions out of its final state even self loops Existence of a Clean NFA Proposition For any NFA M there is an equivalent clean NFA N Proof If M is not clean then we can clean it up by adding two additional states gt a new start state with a single c transition to M39s original start state which is no longer the start state and gt a new final state with c transitions from all of M39s original final states which are no longer final states to the new final state The new NFA is obviously clean and a simple informal argument shows that it is equivalent to the original M Q Give clean NFAs for concatenation and union series and parallel connections respectively as well as for the Kleene closure Theory of Computation Lecture 19 Class NP Max Alekseyev University of South Carolina April 21 2009 Hard V Problems Form Complexity Classes For some problems it is possible to optimize bruteforce solution and obtain a polynomial running time solution eg via dynamic programming But for some other problems there is no simple way to obtain polynomial solution and it is even not known if a polynomial time solution exists However these supposedly hard problems are not independent Many of them form classes such that a polynomial solution to one problem from a class can be used to solve every other problem from the same class in polynomial time Hamiltonian Path A Hamiltonian path in a directed graph G is a directed path that goes through each node in G exactly once HAMPATH 675 t l G is a directed path graph with a Hamiltonian path from s to t gt It is easy to construct an exponential time solution to HAMPATH Q how gt No polynomial time algorithm is known for HAMPATH Polynomial Verifiability Despite that nobody knows how to find a Hamiltonian path in a given graph efficiently once such a path is found it is very easy to verify it is indeed a Hamiltonian path This property is called polynomial verifiability Q Prove that HAMPATH is polynomial verifiable Polynomial Verifiability Despite that nobody knows how to find a Hamiltonian path in a given graph efficiently once such a path is found it is very easy to verify it is indeed a Hamiltonian path This property is called polynomial verifiability Q Prove that HAMPATH is polynomial verifiable Q Prove that the following problem is polynomial verifiable COMPOSITES X l X pq7 for integers p7 q gt1 Polynomial Verifiability Despite that nobody knows how to find a Hamiltonian path in a given graph efficiently once such a path is found it is very easy to verify it is indeed a Hamiltonian path This property is called polynomial verifiability Q Prove that HAMPATH is polynomial verifiable Q Prove that the following problem is polynomial verifiable COMPOSITES X l X pq7 for integers p7 q gt1 Note that some problems may not be polynomial verifiable For example it is not clear how to prove that HAMPATH is polynomial verifiable ie to prove that there is no Hamiltonian path in a given graph Polynomial Verifiability Definition A verifier for a language A is an algorithm V such that A W i V accepts W7 6 for some 6 In other words for every string W E A there exists a certificate or proof 6 such that V accepts W7 6 Polynomial Verifiability Definition A verifier for a language A is an algorithm V such that A W l V accepts W7 6 for some 6 In other words for every string W E A there exists a certificate or proof 6 such that V accepts W7 6 We measure time of a verifier only in terms of W Definition A polynomial time verifier runs in polynomial time in the length of W A language A is polynomial time verifiable if it has a polynomial time verifier Class NP Definition NP is the class of languages that have polynomial time verifiers Problems in NP are called NP problems The term NP stands for nondeterministic polynomial time due to the following theorem Theorem A language is in NP if and only ifit is decided by some nondeterministic polynomial time Turing machine see Theorem 720 on p 266 in Sipser Nondetermi nistic Time Complexity Definition NTIMEtn L l L is a language decided by a Otn time nondeterministic Turing machine As a corollary from the previous theorem we have NP U NTIMEnk k0 Examples of NP problems CLIQUE ltG7 k G is an undirected graph with a k clique SUBSETi SUM lt57 r 5 X1Xk and for some Y177 57 we haVe Zyi f P vs NP lnformally speaking gt P is the class of languages for which membership can be decided quickly gt NP is the class of languages for which membership can be verified quickly Q Prove that P Q NP 7 P vs NP lnformally speaking gt P is the class of languages for which membership can be decided quickly gt NP is the class of languages for which membership can be verified quickly Q Prove that P Q NP 7 It is not known whether there exist languages from NP that are not in P In other words it is not known if P NP or P 7 NP Establishing inequality of the two classes is a famous open problem from the Millennium Problems list with 1M prize P vs NP lnformally speaking gt P is the class of languages for which membership can be decided quickly gt NP is the class of languages for which membership can be verified quickly Q Prove that P Q NP 7 It is not known whether there exist languages from NP that are not in P In other words it is not known if P NP or P 7 NP Establishing inequality of the two classes is a famous open problem from the Millennium Problems list with 1M prize The best currently known way to solve NP problems are variations of brute force leading to exponential algorithms NP g EXPTIME U TIME2quot k0 Theory of Computation Introduction Max Alekseyev University of South Carolina January 13 2009 Outline The Lecturer The Course Goals Evaluation Mathematical Background Sets Sequences and Tuples Functions and Relations The Lecturer Name Max Alekseyev Brief bio gt 2009 Assistant Professor at USC gt 2007 PhD in Computer Science UCSD gt 1999 MS in Mathematics UNN Russia Research interests Computational Molecular Biology Bioinformatics Comparative Genomics Graph Theory Discrete quot39 quotL C 39 Email maxa csescedu Home page httpwwwcsesceduquotmaxal Office Swearingen 3A17 The Course Title Theory of Computing Textbook M Sipser Introduction to the Theory of Computation Second Edition Thomson 2006 Home page httpwwwcsescedumaxalcsce551 Discussion board TBA Office hours TTh 330 430pm Goals 4 39rapahilitie and limitation of computers Explore Understand what is computing what can or cannot be computed Determine the cost of computing in terms of available resources Classify computational problems into easy and hard Evaluation Evaluation of a student39s progress is based on hisher ability to understand and solve problems Evaluation Evaluation of a student39s progress is based on hisher ability to understand and solve problems Understanding of a problem is a clear vision of what is given what is asked and what would constitute a solution Evaluation Evaluation of a student39s progress is based on hisher ability to understand and solve problems Understanding of a problem is a clear vision of what is given what is asked and what would constitute a solution Solving a problem implies finding a solution as well as convincing arguments proof that support this solution Evaluation Evaluation of a student39s progress is based on hisher ability to understand and solve problems Understanding of a problem is a clear vision of what is given what is asked and what would constitute a solution Solving a problem implies finding a solution as well as convincing arguments proof that support this solution Solving is not possible without understanding However understanding without being able to solve is possible Sets A set is a group of objects called elements or members of this set For example the students in this room form a set Sets A set is a group of objects called elements or members of this set For example the students in this room form a set A set can be defined by listing all its elements inside braces eg s 72157 The order and repetitions of elements in sets do not matter in particular 721572151721757121 Sets A set is a group of objects called elements or members of this set For example the students in this room form a set A set can be defined by listing all its elements inside braces eg s 72157 The order and repetitions of elements in sets do not matter in particular 721572151721757121 The membership is denoted by E symbol For example 21 E 5 but 10 5 For two sets A and B we say A is a subset of B and write A Q B if every member of A is also a member of B We say that A is a proper subset of B and write A g B if A is a subset of B and not equal to B Sets A set is a group of objects called elements or members of this set For example the students in this room form a set A set can be defined by listing all its elements inside braces eg s 72157 The order and repetitions of elements in sets do not matter in particular 721572151721757121 The membership is denoted by E symbol For example 21 E 5 but 10 5 For two sets A and B we say A is a subset of B and write A Q B if every member of A is also a member of B We say that A is a proper subset of B and write A g B if A is a subset of B and not equal to B Q How many distinct subsets are there in the set 5 How many of them are proper Sets A set is a group of objects called elements or members of this set For example the students in this room form a set A set can be defined by listing all its elements inside braces eg s 72157 The order and repetitions of elements in sets do not matter in particular 721572151721757121 The membership is denoted by E symbol For example 21 E 5 but 10 5 For two sets A and B we say A is a subset of B and write A Q B if every member of A is also a member of B We say that A is a proper subset of B and write A g B if A is a subset of B and not equal to B Q How many distinct subsets are there in the set 5 How many of them are proper The set of all subsets of a set A is called the power set of A and denoted 2A Examples of Sets The set with no elements is called the empty set and denoted Q The empty set is a subset of any other set Examples of Sets The set with no elements is called the empty set and denoted Q The empty set is a subset of any other set The set of natural numbersN or N N 123 Examples of Sets The set with no elements is called the empty set and denoted Q The empty set is a subset of any other set The set of natural numbersN or N N 123 The set of integers Z or Z Z 7271012 It is clear that N Q Z Examples of Sets The set with no elements is called the empty set and denoted Q The empty set is a subset of any other set The set of natural numbersN or N N 123 The set of integers Z or Z Z 7271012 It is clear that N Q Z The set of perfect squares n l n m2 for some m E N is a subset of both N and Z Examples of Sets The set with no elements is called the empty set and denoted Q The empty set is a subset of any other set The set of natural numbersN or N N 123 The set of integers Z or Z Z 7271012 It is clear that N Q Z The set of perfect squares n l n m2 for some m E N is a subset of both N and Z The number of elements in a set A is called the cardinality or size of the set and denoted by We have Ml O and Wi lZl oo Q For a finite set A what is l2Al Set Operations For given two sets A and B one can define the following set operations Union A U B Example 123 U 13 5 12 35 Intersection A O B Example 123 13 5 13 Difference A B Example 1 2 3 1 3 5 In the case of B C A the result of A B is also called the complement of B in A and denoted B Set Operations For given two sets A and B one can define the following set operations Union A U B Example 123 U 13 5 12 35 Intersection A O B Example 123 13 5 13 Difference A B Example 1 2 3 1 3 5 In the case of B C A the result of A B is also called the complement of B in A and denoted B The Venn diagram is a convenient way to illustrate the set operations Sequences and Tuples A sequence is a list of objects in some order For example sequences of the students39 names in alphabetic order such as Alice Bob In contrast to sets repetitions and order matter in sequences The sequences 7217 57 and 77 7217 57 are not equal Finite sequences are called tuples In particular a sequence with k elements is called k tuple as well as pair triple quadriple etc Sequences and Tuples A sequence is a list of objects in some order For example sequences of the students39 names in alphabetic order such as Alice Bob In contrast to sets repetitions and order matter in sequences The sequences 721 57 and 7 721 57 are not equal Finite sequences are called tuples In particular a sequence with k elements is called k tuple as well as pair triple quadriple etc All k tuples X1X2 Xk where X is taken from the set A form a set A1 x A2 x Ak called the Cartesian product or cross product of the sets A1A2 Ak For example if A1 p q and A2 12 3 then A1 X A2 P717P727P737q717q727q73 II III Ell Functions A function mapping f sets up a correspondence between the elements of one set A and elements of the other set B written f A a B In particular if an element a E A corresponds to an element b E B under the function f we write fa b where a is called the input or argument and b is called the output or value of f Functions A function mapping f sets up a correspondence between the elements of one set A and elements of the other set B written f A a B In particular if an element a E A corresponds to an element b E B under the function f we write fa b where a is called the input or argument and b is called the output or value of f The set A is called the domain of f while the set B is called the range of f Functions A function mapping f sets up a correspondence between the elements of one set A and elements of the other set B written f A a B In particular if an element a E A corresponds to an element b E B under the function f we write fa b where a is called the input or argument and b is called the output or value of f The set A is called the domain of f while the set B is called the range of 1 For a finite set A the function f A a B can be defined by a table of its values of elements of A For example for A Z5 0172374 the set of integers modulo 5 a function f I Z5 Z5 Types of Functions A function f A1 x A2 x x Ak B is called a k ary function Unaty functions correspond to the case k 1 while binary functions correspond to the case k 2 Types of Functions A function f A1 x A2 x x Ak B is called a k ary function Unaty functions correspond to the case k 1 while binary functions correspond to the case k 2 A function f A TRUE7 FALSE is called a predicate or property For example the property even defines evenness of a given integer even4 TRUE and even5 FALSE Types of Functions A function f A1 x A2 x x Ak B is called a k ary function Unaty functions correspond to the case k 1 while binary functions correspond to the case k 2 A function f A TRUE7 FALSE is called a predicate or property For example the property even defines evenness of a given integer even4 TRUE and even5 FALSE A property f A x A x x A TRUE7 FALSE whose domain is the set of k tuples is called k ary relation on A An example is the beats relation between scissors paper and stone see p9 in Sipser Types of Functions A function f A1 x A2 x x Ak B is called a k ary function Unaty functions correspond to the case k 1 while binary functions correspond to the case k 2 A function f A TRUE7 FALSE is called a predicate or property For example the property even defines evenness of a given integer even4 TRUE and even5 FALSE A property f A x A x x A TRUE7 FALSE whose domain is the set of k tuples is called k ary relation on A An example is the beats relation between scissors paper and stone see p9 in Sipser For binary relation R we often use infix notation writing XRy instead of RX7 y TRUE Equivalence Relation A binary relation R on a set A is called an equivalence relation if R Is Reflexive for every X E A XRX Symmetric for every Xy E A XRy implies yRX Transitive for every Xyz E A XRy and sz implies XRz The equality relation is an example of equivalence relation Equivalence Relation A binary relation R on a set A is called an equivalence relation if R Is Reflexive for every X E A XRX Symmetric for every Xy E A XRy implies yRX Transitive for every Xyz E A XRy and sz implies XRz The equality relation is an example of equivalence relation Q What other equivalence relations you know Equivalence Relation A binary relation R on a set A is called an equivalence relation if R Is Reflexive for every X E A XRX Symmetric for every Xy E A XRy implies yRX Transitive for every Xyz E A XRy and sz implies XRz The equality relation is an example of equivalence relation Q What other equivalence relations you know Q Is the relation less or equal an equivalence relation Thanks Theory of Computation Lecture 5 Regular Expressions Max Alekseyev University of South Carolina January 29 2009 Lectu re Outline Regular expressions Regular Expressions and Regular Languages Generalized NFA Atomic Regular Expressions Let X be a fixed alphabet A regular expression or regexp for short is an expression that describes a particular language over X If r is a regular expression we write Lr for the language described by r We may also just use the regexp itself in place of the language it describes Primitive atomic regular expresions are gt 0 describes the empty language L 0 gt 6 describes the language L 6 consisting ofjust the empty string and gt a for a E X describes the language La 3 consisting of just the string a of length 1 Regular Expressions Regular expressions can be combined with three possible operators union concatenation and Kleene closure If r and s are regexps then so are gt r U s describing the language Lr U Ls gt rs describing the language LrLs gt r describing the language Lr Every regular expression is contructed by these rules no other regular expressions are possible This is an inductive recursive definition since it defines new regular expressions in terms of shorter ones subexpressions Conventions Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences r before r before rs before r U 5 Both binary operations are associative so we don39t care how they associate We will use rJr as a shorthand for rr ie denoting concatination of 1 or more strings from r Q What is rU67 Conventions Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences r before r before rs before r U 5 Both binary operations are associative so we don39t care how they associate We will use rJr as a shorthand for rr ie denoting concatination of 1 or more strings from r Q What is rU67 k Similarly we will use r as a shorthand for rr r Rd Examples of Regular Expressions Let X 01 010 W wcontains a singlel X1X W wcontains at least onel Examples of Regular Expressions Let X 01 010 W l WCOntains a singlel X1X W l WCOntains at least onel XX W l the length ofWis even XXX W l the length ofWis multiple of 3 Examples of Regular Expressions Let X 01 010 W l WCOntains a singlel X1X W l WCOntains at least onel XX W l the length ofWis even XXX W l the length ofWis multiple of 3 Q What is 01 7 Examples of Regular Expressions Let X 01 010 W l WCOntains a singlel X1X W l WCOntains at least onel XX W l the length ofWis even XXX W l the length ofWis multiple of 3 Q What is 01 7 0X001X10001w WStarts and ends with the same symbol 0U a 01 U1 0U 61 U 8 80 101 Examples of Regular Expressions Let X 01 010 W l WCOntains a singlel X1X W l WCOntains at least onel XX W l the length ofWis even XXX W l the length ofWis multiple of 3 Q What is 01 7 0X001X10001w WStarts and ends with the same symbol 0U a 01 U1 0U 61 U 8 80 101 1 0 0 6 Regular Languages and RegEXps From the names it is not surprising that Theorem A language is regular if and only if some regular language describes it There are actually two statements to prove gt Every regular expression describes some regular language gt Every regular language is described by some regular expression One of them is rather obvious Q Which one From RegEXps to NFAs Theorem Every regular expression describes some regular language Recall that regexps are defined recursively To prove that regexps describe regular languages it is enough to prove this for atomic regexps and use the fact the union concatenation and Kleene closure operations preserve regularity see Sipser p 67 The actual proof could be done by induction on the length of the regexp From NFAs to RegEXps Theorem Every regular language is described by some regular expression The proof is done by construction of a regular expression for a language A given an NFA recognizing A The construction uses a generalized form of NFA GN FA So transforming an NFA to an equivalent regexp will be done as follows NFA GNFA RegEXp Generalized NFA Definition Let REGEXP be the set of all regular expressions A generalized nondeterministic finite automaton GN FA is a tuple G Q7 Z6 qo F where gt Q is a finite set the set of states gt X is a finite alphabet gt L70 6 Q the start state gt F Q Q the set of final states and gt 6 Q x Q a REGEXP is the transition function The transition diagram for a GNFA is the same for an NFA except that there is exactly one edge from each state q to each state r and the edges are labeled with regular expressions the edge 77 r being labeled with 6q7 r The edges labeled with the regexp Q can be omitted from the diagram as they can never be followed G N FA Computation A complete accepting computation can be defined for GNFAs analogously to the case of NFAs The idea is that you can follow an edge by reading a prefix of the remaining input that matches the edges label ie you read a string that is in the language denoted by the label which is a regexp Definition Let G Q7X767 qo7 F be a GNFA and let W E X be a string We say that G accepts W if there exist strings W17 7 Wk 6 X and states so7 5k 6 Q for some k 2 0 such that gt W W1 Wk gt 50 70 gt 5k 6 F and gt W E L6s1s for all 1 k The language recognized by G denoted LG is the set of all strings over X accepted by G From NFA to GNFA We will find it convenient to work with a clean GNFA that has a start state with no incoming transitions and a single final state that has no outgoing transitions So our goal is to contruct an equivalent clean GNFA from a given NFA 1 Given an NFA we first transform it to a clean NFA M 2 The states GNFA G that we are constructing are the same as in M with the same starting and final states 9quot For any two states p and q if there is a transition p a q labelled X1 Xk in M we define a transition p a q labelled by a regexp X1 U ka in G if there is no transition p a q in M we define a transition p a q labelled by a regexp Q in G Q Are we done From NFA to GNFA We will find it convenient to work with a clean GNFA that has a start state with no incoming transitions and a single final state that has no outgoing transitions So our goal is to contruct an equivalent clean GNFA from a given NFA 1 Given an NFA we first transform it to a clean NFA M 2 The states GNFA G that we are constructing are the same as in M with the same starting and final states 9quot For any two states p and q if there is a transition p a q labelled X1 Xk in M we define a transition p a q labelled by a regexp X1 U ka in G if there is no transition p a q in M we define a transition p a q labelled by a regexp Q in G Q Prove that M and G are equivalent How From NFA to GNFA We will find it convenient to work with a clean GNFA that has a start state with no incoming transitions and a single final state that has no outgoing transitions So our goal is to contruct an equivalent clean GNFA from a given NFA 1 Given an NFA we first transform it to a clean NFA M 2 The states GNFA G that we are constructing are the same as in M with the same starting and final states 9quot For any two states p and q if there is a transition p a q labelled X1 Xk in M we define a transition p a q labelled by a regexp X1 U ka in G if there is no transition p a q in M we define a transition p a q labelled by a regexp Q in G Q Prove that for every computation in M there exists an equivalent computation in G and vice versa From GNFA to RegExp If a constructed GNFA G hasjust two states we are done Q why From GNFA to RegExp If a constructed GNFA G hasjust two states we are done Q why7 For a constructed GNFA G with k gt 2 we will eliminate states other than the start and final ones one by one and modify the transitions such that a new GNFA G with k7 1 states is equivalent to the original one From the resulting GN FA with two states we will derive a regexp as above From GNFA to RegExp If a constructed GNFA G hasjust two states we are done Q why7 For a constructed GNFA G with k gt 2 we will eliminate states other than the start and final ones one by one and modify the transitions such that a new GNFA G with k7 1 states is equivalent to the original one From the resulting GN FA with two states we will derive a regexp as above gt Select any state which we denote qp other than the start and final states gt GNFA G has the same states as G except qp gt For any two other states q and qj let r1 6q7 qp r2 6qrip7 hip r3 6qrip7 71 afld r4 6qi7 qrip ln 6 transition from q to qj is labeled r4 U rlrgrg see Sipser p Theory of Computation Lecture 7 Context free Grammar Max Alekseyev University of South Carolina February 9 2009 Lectu re Outline Context free Grammars Derivation Context free Languages Parse Trees and Ambiguity Chomsky Normal Form Languages with Recursive Structure Consider a language L 0 1 l n 2 0 As we already know this language is not regular However it can be generated by simple recursive rules gt 6 E L gt for a string 5 from L the string 051 is also in L That is applying these rules and starting with 6 E L we will get that the strings 01 0011 000111 and so on are also in L Sooner or later we will obtain every element of L Languages with Recursive Structure Consider a language L 0 1 l n 2 0 As we already know this language is not regular However it can be generated by simple recursive rules gt 6 E L gt for a string 5 from L the string 051 is also in L That is applying these rules and starting with 6 E L we will get that the strings 01 0011 000111 and so on are also in L Sooner or later we will obtain every element of L Context free grammar is a powerful tool to describe languages with recursive structure Example of a Context free Grammar gt e e L gt for a string 5 from L the string 051 is also in L can be formally written as substitution rules 5H5 gt01 where at the left hand side we have variables usually denoted by capital letters such as 5 in this case symbols other than variables are called terminals The top most variable is called the start varible The set of rules the set of terminals and the set of varibles with one marked as the start variable form a context free grammar Example of a Context free Grammar gt e e L gt for a string 5 from L the string 051 is also in L can be formally written as substitution rules 5H5 gt01 where at the left hand side we have variables usually denoted by capital letters such as 5 in this case symbols other than variables are called terminals The top most variable is called the start varible The set of rules the set of terminals and the set of varibles with one marked as the start variable form a context free grammar The set of rules corresponding to the same variable can be written in a single line eg 5 gt 051 l 6 Context free Grammars A context free grammar CFG is a 4 tuple V7 X R7 5 where gt V is a finite set of variables gt X is a finite set of terminals disjoint from V gt R is a finite set of substitution rules each rule maps a variable into a string of variables and terminals gt 5 E V is the start variable The term context free reflects the fact that each variable can be substituted independently of the context in which it appears Context free Grammars A context free grammar CFG is a 4 tuple V7 X R7 5 where gt V is a finite set of variables gt X is a finite set of terminals disjoint from V gt R is a finite set of substitution rules each rule maps a variable into a string of variables and terminals gt 5 E V is the start variable The term context free reflects the fact that each variable can be substituted independently of the context in which it appears Q Can we say that R V a V U XV ie R is a function from V to the set of strings over variables and terminals Context free Grammars A context free grammar CFG is a 4 tuple V7 X R7 5 where gt V is a finite set of variables gt X is a finite set of terminals disjoint from V gt R is a finite set of substitution rules each rule maps a variable into a string of variables and terminals gt 5 E V is the start variable The term context free reflects the fact that each variable can be substituted independently of the context in which it appears Q Can we say that R V a V U XV ie R is a function from V to the set of strings over variables and terminals Q What39s about R V a 73 V U XV Derivation Substitution rules is convenient way to represent a context free grammar A gt 041 A gt B B a Q What are VX7 R75 for this grammar Derivation Substitution rules is convenient way to represent a context free grammar A gt 0A1 A gt B B a Q What are VX7 R75 for this grammar A derivation of a string W in a given grammar G is a sequence of substitutions starting with the start symbol and resulting in W eg A 0A1 00A11 000A111 0008111 000111 is a derivation of the string 000111 in the grammar defined above The symbol a reads yields Derivation Substitution rules is convenient way to represent a context free grammar A gt 0A1 A gt B B a Q What are VX7 R75 for this grammar A derivation of a string W in a given grammar G is a sequence of substitutions starting with the start symbol and resulting in W eg A 0A1 00A11 000A111 0003111 000111 is a derivation of the string 000111 in the grammar defined above The symbol a reads yields We say u derives v and write u 3 v if there is a derivation for some k 2 0 LIgtLI1gtLI2gtgtLIkgtV Context free Languages The set of all strings that can be derived generated in a given grammar G V7 X R7 5 is called the language of the grammar G and denoted LG In other words LGWi5gtw A language is called a context free language CFL if it is generated by some context free grammar We already considered two examples of context free languages LGl0 1 ln 2 O and LGg0 1 ln 2 0 Context free Languages The set of all strings that can be derived generated in a given grammar G V7 X R7 5 is called the language of the grammar G and denoted LG In other words LGWi5gtw A language is called a context free language CFL if it is generated by some context free grammar We already considered two examples of context free languages LGl0 1 ln 2 O and LGg0 1 ln 2 0 Given two CFLs it is easy to construct a CFG for their union eg combining CFGs for LGl and LGg 5 gt 51 l 52 1 gt 0511l6 2 gt 0521l From DFA to CFG CFGs have more power that DFA It is not surprising that for any DFA recognizing a language L we can construct into a CFG generating the same language L Q What such construction would prove From DFA to CFG CFGs have more power that DFA It is not surprising that for any DFA recognizing a language L we can construct into a CFG generating the same language L Q What such construction would prove For a given DFA Q7X767 qo7 F an equivalent CFG can be constructed as follows gt Introduce the variable R for every state q E Q gt Make R0 a start variable of the CFG gt Add the rule R H aRj for every transition q i qj defined by 6 ie 6q7 a qj gt Add the rule R H 6 if q is an accepting state Q Verify that the constructed CFG generates the same language as the recognized by the given DFA Parse Trees and Ambiguity A parse tree is a convenient way to represent a derivation of a particular string see Sipser p101 and 103 The same parse tree may correspond multiple different derivations However each parse tree uniquely defines a leftmost derivation where at every step the leftmost remaining variable is being replaced Parse Trees and Ambiguity A parse tree is a convenient way to represent a derivation of a particular string see Sipser p101 and 103 The same parse tree may correspond multiple different derivations However each parse tree uniquely defines a leftmost derivation where at every step the leftmost remaining variable is being replaced A string W is derived ambiguoust in a context free grammar G if it has two or more different leftmost derivation thus parse trees A grammar G is ambiguous if it generates some string ambiguously Parse Trees and Ambiguity A parse tree is a convenient way to represent a derivation of a particular string see Sipser p101 and 103 The same parse tree may correspond multiple different derivations However each parse tree uniquely defines a leftmost derivation where at every step the leftmost remaining variable is being replaced A string W is derived ambiguousy in a context free grammar G if it has two or more different leftmost derivation thus parse trees A grammar G is ambiguous if it generates some string ambiguously Sometimes for an ambiguous grammar there exists an unambiguous grammar generating the same language But some languages can be generated only by ambiguous grammars Such languages are called inherently ambiguous In particular the language aibjck l ij Vj k is inherently ambiguous Chomsky Normal Form A CFG is Chomsky normal form may have rules only of the following forms 5 gt 5 A a BC A gt a where 5 is the start variable A B and C are any varibles except that B 7 5 and C 7 5 and a is any terminal Theorem Every CFL is generated by some CFG in Chomsky normal form Theory of Computation Lecture 12 Decidable Languages Max Alekseyev University of South Carolina March 3 2009 Turing Machine Languages Recall that a collection of strings that a TM M accepts is called the language ofM or language recognized by M denoted LM Definition A language is Turing recognizable or recursively enumerable if it is recognized by some Turing machine Turing Machine Languages Recall that a collection of strings that a TM M accepts is called the language ofM or language recognized by M denoted LM Definition A language is Turing recognizable or recursively enumerable if it is recognized by some Turing machine A TM M on an input that is not in LM can either reject or loop We distinguish TMs that never loop and call them deciders A decider M decides the language that it recognizes Definition A language is decidable or recursive if it is decided by some Turing machine It is easy to see that the complement of a decidable language is also decidable Decidable Languages concerning RL Acceptance problems ADFA ltB7 W B is a DFA that accepts string W ANFA ltB7 W B is an NFA that accepts string W AREX ltR7 W R is a regexp that generates string W Emptiness testing EDFA A is a DFA and LA 0 Equality testing EQDFA ltA7 B A7 Bare DFAs and LA LB Deciding a Language ADFA lt87 Wgt i B is a DFA that accepts string W We need to present a TM that decides ADFA Idea is to execute given B on the given input W within our TM Q Is that possible Deciding a Language ADFA ltB7 Wgt l B is a DFA that accepts string W We need to present a TM that decides ADFA Idea is to execute given B on the given input W within our TM Q Is that possible Check points gt Check that input represent a valid DFA B a list of five components Q X 6 qo and F and a valid string W over the alphabet of B ie X gt Check that TM is able to store and maintain the configuration of B somewhere on its tape gt Check that transitions from state to state in B can be done in a finite number of steps in TM gt Check that execution of B on W will terminate at some point Decidable Languages concerning RL ANFA lt37 Wgt i B is an NFA that accepts string W AREX ltR7 Wgt i R is a regexp that generates string W Idea is to construct a TM that first converts a given NFA or regexp into an equivalent DFA and then executes this DFA as before Decidable Languages concerning RL EDFA l A is a DFA and LA 0 Idea is to construct a TM that view given DFA A as a directed graph with verices states and edgestransitions and explores all paths from the start state in this graph If it finds a path connecting the start state to some accepting state of A it accepts otherwise if there are no such path it rejects Decidable Languages concerning RL EQDFA ltA7 B l A7 Bare DFAs and LA LB First notice that LA LB is equivalent to emptiness of both set differences LA LB LA LB and LB LA LB and thus their union MA n W U MB n W called the symmetric difference of LA and LB The symmetric difference is a result of regular operations over LA and LB thus it represents a regular language recognized of some DFA C Therefore we can design a TM that first constructs a DFA C from the given DFAs A and B and then tests emptiness for LC Decidable Languages concerning CFL ACFG ltG7 Wgt i G is a CFG that generates string W Emptiness testing ECFG i G is a CFG and LG 0 But equality testing for CFG is NOT decidable EQCFG ltG7 H i G7 Hare CFGs and LG LH CFL is decidable Theorem Every context free language is decidable Relationship among languages RL C CFL C DECIDABLE C RECOGNIZABLE Turingrecognizable decidable context free regular Theory of Computation Lecture 20 NP complete problems Max Alekseyev University of South Carolina April 21 2009 NP Complete Problems b V V For some problems in NP there is no simple way to obtain polynomial solution and it is even not known if a polynomial time solution exists However these supposedly hard problems are not independent Many of them form classes such that a polynomial solution to one problem from a class can be used to solve every other problem from the same class in polynomial time The hardest problems in NP are called NP complete Finding a polynomial time algorithm for an NP complete problem would imply a polynomial algorithm for any other problem in NP Importance of NP complete Problems gt From theoretical perspective proving that there exists or not exists a polynomial algorithm for a particular NP complete problem would imply existence or non existence of polynomial algorithms for the other problems in NP ie NP P or NP 7 P gt From practical perspective knowing that a certain problem is NP complete may prevent wasting time searching for a nonexistent polynomial time algorithm While we don39t know for sure whether NP P or NP 7 P in practical problems it is wise to believe that NP 7 P Boolean Expressions and Satisfiability Recall that variables that take only values TRUE 1 and FALSE O are called Boolean variables Boolean operations conjunction AND A disjunction OR V exclusive or XOR addition modulo 2 63 equality equivalence ifF if and only if lt gt lAllOlll lVllOlll lEBllOlll ls llOlll lOllOlOl llOlll lOllOlll lollllOl llllOlll llllllll llllllOl llllOlll T implicationa Other Boolean operations negation NO Boolean Expressions and Satisfiability Recall that variables that take only values TRUE 1 and FALSE O are called Boolean variables Boolean operations conjunction AND A disjunction OR V exclusive or XOR addition modulo 2 63 equality equivalence ifF if and only if lt gt lAllOlll lVllOlll l ll0l1l lHllOlll lOllOlOl lOllOlll lOllOlll lollllOl llllOlll llllllll llllllOl llllOlll Other Boolean operations negation NOT 7 implication a A Boolean formula is an expression involving Boolean variables and operations eg gt YAy v xAE A Boolean formula is satisfiable if there exists an assignment of Us and ls to the variables that makes the formula evaluate to 1 For example 1 is satisfiable because the assignment X 0 y 1 and z 0 makes 1 evaluate to 1 Satisfiability Problem SAT The satisfiabilty problem is to test whether a Boolean formula is satisfiable SAT l j is a satisfiable Boolean formula Q Prove that SAT 6 NP Satisfiability Problem SAT The satisfiabilty problem is to test whether a Boolean formula is satisfiable SAT l j is a satisfiable Boolean formula Q Prove that SAT 6 NP Theorem Cook Levin SAT 6 P ifand only ifP NP Polynomial Time Computable Functions A function f X a X is called a polynomial time computable function if some polynomial time Turing machine on every input W halts with just fW on its tape Q How this is different from the definition of computable function Polynomial Time Red ucibility Definition Language A is polynomial time reducible to language B written A p B if there is a polynomial time computable function f X a X such that for every W W AltgtfweB The function f is called the polynomial time reduction of A to B Polynomial Time Reducibility Definition Language A is polynomial time reducible to language B written A gp B if there is a polynomial time computable function f Zquot a Xquot such that for every w WEAltgtfWEB The function f is called the polynomial time reduction of A to B Polynomial Time Red ucibility Definition Language A is polynomial time reducible to language B written A p B if there is a polynomial time computable function f X a X such that for every W W E A ltgt fW e B The function f is called the polynomial time reduction of A to B Polynomial time reduction provides a way to convert in polynomial time a decision problem for language A into a decision problem for B Instead of testing whether W E A one can compute fW and test whether fW E B If one problem is polynomial time reducible to another known to have polynomial time solution one can thereby obtain a polynomial solution to the original problem Theorems Theorem IfA p B ifand only ifZ p E Theorem Ingp B andB E P thenA E P Q How would you prove these theorems NP Complete Problems Definition A language B is NP complete if the following two conditions hold 1 B E NP 2 for every A E NP A p B NP Complete Problems Definition A language B is NP complete if the following two conditions hold 1 B E NP 2 for every A E NP A p B Theorem IfB is NP complete and B E P then P NP NP Complete Problems Definition A language B is NP complete if the following two conditions hold 1 B E NP 2 for every A E NP A p B Theorem IfB is NP complete and B E P then P NP Theorem IfB is NP complete C E NP and B p C then C is NP complete SAT is NP Complete Theorem SAT is NP complete see Theorem 737 on p276 in Sipser 3SAT gt A literal is a Boolean variable or its negation gt A clause is several variables connected V39s eg nvaEvm gt A conjunctive normal form or cnf formula consists of several clauses connected with As eg nvEVKVMywmvamywmvgy gt A 3cnf formula consists of several clauses each with exactly 3 literals eg nvzvzywavzvkquvgvnywnvampvky 3SAT gt A literal is a Boolean variable or its negation gt A clause is several variables connected V39s eg nvaEvm gt A conjunctive normal form or cnf formula consists of several clauses connected with As eg nvEVKVMywmvamywmvgy gt A 3cnf formula consists of several clauses each with exactly 3 literals eg nvzvzywavzvkquvgvnywnvampvky Let 3AT l j is a satisfiable 3cnf formula 3SAT is NP complete Recall that SAT l j is a satisfiable Boolean formula 3AT l j is a satisfiable 3cnf formula Theorem SAT gp 3AT Proof ideas gt every Boolean formula formula can be converted into an equivalent cnf formula in polynomial time gt every cnf formula can be converted into an equivalent 3cnf formula by splitting clauses with more than 3 literals into shorter ones eg X1 VXQ VX3 VX4 is equivalent to X1 VXQ Vz A EVXg VX4 see also Theorem 742 on p282 in Sipser CLQUE is NP Complete Recall that 3AT i j is a satisfiable 3cnf formula CLIQUE ltG7 k i G is an undirected graph with a k clique Theorem 3AT gp CLIQUE

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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

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