lecture notes on Theory of computation

How to learn Theory of Computation and theory of computation finite automata examples pdf free example
NathanBenett Profile Pic
Published Date:11-07-2017
Your Website URL(Optional)
Lecture notes of CS273: Introduction to the Theory of Computation Spring Semester, 2008 and CS373: Theory of Computation Spring Semester, 2009 CS, UIUC 1 Margaret Fleck Sariel Har-Peled May 18, 2009 1 Department of Computer Science; University of Illinois; 201 N. Goodwin Avenue; Urbana, IL, 61801, USA; sarieluiuc.edu; http://www.uiuc.edu/sariel/.Chapter 1 Lecture 1: Overview and Administrivia 20 January 2009 1.1 Course overview The details vary from term to term. This is a rough outline of the course and a motivation for why we study this stuff. 1. Theory of Computation.  Build formal mathematical models of computation.  Analyze the inherent capabilities and limitations of these models. 2. Course goals:  Simple practical tools you can use in later courses, projects, etc. The course will provide you with tools to model complicated systems and analyze them.  Inherent limits of computers: problems that no computer can solve.  Better fluency with formal mathematics (closely related to skill at debugging programs). 3. What is computable? (a) check if a number n is prime (b) compute the product of two numbers (c) sort a list of numbers (d) find the maximum number from a list 4. Computability, complexity, automata. 5. Example: input n; assume n1; while (n =1) if (n is even) n := n/2; else n := 3n+1; 17Does this program always stop? Not known. 6. Course divides into three sections  regular languages ———— practical tools  context-free languages  Turing machines. 7. Turing machines and decidability limits of computation. Regular languages Context free languages Turing decidable languages Turing recognizable language Not Turing recognizable languages 8. Regular languages and context-free languages:  Simple and computationally efficient.  heavily used in programming languages and compilers.  also in computational linguistics.  well-known application: grep 9. Difference in scope  regular languages describe tokens (e.g. what is a legal variable name?)  context-free languages describe syntax (whole program, whole sentence) Illustrate with your favorite example from programming languages or natural language. 10. State machines  widely used in other areas of CS (e.g. networking)  equivalent to regular languages (we will see later in course)  used to implement algorithms for regular languages e.g. grep. Illustrate with your favorite simple state machine, e.g. a vending machine. 11. Decidability:  Are there problems that computers can not solve?) yes  By the end of the course, you will know why. Example: the CS 225 grader problem. – Given a random C program (maybe very badly written). – Will it stop or will it keep running forever? – Will it return the right answer for all possible inputs? 12. Models of mathematics  19th century - major effort to formalize calculus.  Georg Cantor - starts set theory. Proves that the “number” of integers is strictly smaller than the number of integers, using the diagonalization argument. 18 David Hilbert (1920’s) tries to formalize all of math and prove it correct  Kurt Gödel (1931) shows that one can not prove consistency of a mathematical formalism having non-trivial power. 13. Formal models of computation  Alonzo Church: lambda calculus (like LISP).  Alan Turing: Turing machines (very simple computers).  Church/Turing thesis: these models can do anything that any computer can do.  Both showed (1936) that their respective models contain undecidable problems. 14. It is mysterious and “cool” that some simple-looking problems are undecidable. 15. The proofs of undecidability are a bit abstract. Earlier parts of the course will help prepare you, so you can understand the last part. 1.2 Necessary Administrivia This lecture mentions the highlights. Browse the web page for more details: http://www.cs.uiuc.edu/class/sp09/cs373/.  Prerequisites: CS 125, CS 173, CS 225 (or equivalents). Other experience can sometimes substitute (e.g. advanced math). Speak to us if you are not sure.  Vital to join the class newsgroup (details on web page). Carries important announcements, e.g. exam times, hints and corrections on homeworks. Especially see the Lectures page for schedule of topics, readings, quiz/exam dates.  Homework 1 should be available on the class website. Due next Thursday. (Normally they will be due Thursdays on 12:30, but next Monday is a holiday.) Browse chapter 0 and read section 1.1. Normally, homeworks and readings will not be announced in class and you must watch the website and newsgroups.  Read and follow the homework format guidelines on the web page. Especially: each problem on a separate sheet, your name on each problem, your section time (e.g. 10) in upper-right corner. This makes a big difference grading and sorting graded homeworks.  Course staff.  Discussion sections. Office hours will be posted in the near future. Email and the newsgroup are always an option. Please do not be shy about contacting us.  Problem sets, exams, etc are common to all sections. It may be easier to start with your lecture and discussion section instructors, but feel free to also talk to the rest of us.  Sipser textbook: get a copy. We follow the textbook fairly closely. Our lecture notes only outline what was covered and don’t duplicate the text. Used copies, international or first editions, etc are available cheap through Amazon.  Graded work: (a) 30%: Final. (b) 20%: First midterm. (c) 20%: Second midterm. 19(d) 25%: Homeworks and self-evaluations. Worst homework will be dropped. Self evaluations would be online quizes on the web. (e) 5%: Attending discussion section.  Late homeworks are not accepted, except in rare cases where you have a major excuse (e.g. serious illness, family emergency, weather unsafe for travel).  Homeworks can be done in groups of  3 students. Write their names under your own on your homework. Also document any other major help you may have gotten. Each person turns in their own write-up IN THEIR OWN WORDS.  Doing homeworks is vital preparation for success on the exams. Getting help from your partners is good, but don’t copy their solutions blindly. Make sure you understand the solutions.  See the web pages for details of our cheating policy. First offense zero on the exam or assignment involved. Second offense or cheating on the final) fail the course. Please do not cheat.  If you are not sure what is allowed, talk to us and/or document clearly what you did. That is enough to ensure it is not “cheating” (though you might lose points).  Bugs happen, on homeworks and even in the textbook and on exams. If you think you see a bug, please bring it to our attention.  Please tell us if you have any disabilities or other special circumstances that we should be aware of. 20Chapter 2 Lecture 2: Strings, Languages, DFAs 17 January 2008 This lecture covers material on strings and languages from Sipser chapter 0. Also chapter 1 up to (but not including) the formal definition of computation (i.e. pages 31–40). 2.1 Alphabets, strings, and languages 2.1.1 Alphabets An alphabet is any finite set of characters. Here are some examples for such alphabets: (i) f0;1g. (ii) fa;b;cg. (iii) f0;1; g. (iv) fa;:::z;A;:::Zg: all the letters in the English language. (v) ASCII - this is the standard encoding schemes used by computers mappings bytes (i.e., integers in the range 0::255) to characters. As such, a is 65, and the space character ␣ is 32. (vi) fmoveforward;moveback;rotate90;resetg. 2.1.2 Strings This section should be recapping stuff already seen in discussion section 1. A string over an alphabet  is a finite sequence of characters from . Some sample strings with alphabet (say)  =fa;b;cg are abc, baba, and aaaabbbbccc. The length of a string x is the number of characters in x, and it is denoted byjxj. Thus, the length of the string w = abcdef isjwj = 6. The empty string is denoted by , and it (of course) has length 0. The empty string is the string containing zero characters in it. The concatenation of two strings x and w is denoted by xw, and it is the string formed by the string x followed by the string w. As a concrete example, consider x = cat,w = nip and the concatenated strings xw = catnip and wx = nipcat. Naturally, concatenating with the empty string results in no change in the string. Formally, for any string x, we have that x =x. As such  =. For a string w, the string x is a substring of w if the string x appears contiguously in w. As such, for w =abcdef we have that bcd is a substring of w; but ace is not a substring of w: 21A string x is a suffix of w if its a substring of w appearing in the end of w. Similarly, y is a prefix of w if y is a substring of w appearing in the beginning of w. As such, for w =abcdef we have that abc is a prefix of w; and def is a suffix of w: Here is a formal definition of prefix and substring. Definition 2.1.1 The string x is a prefix of a string w, if there exists a string z, such that w =xz. Similarly, x is a substring of w if there exist strings y and z such that w =yxz. 2.1.3 Languages  A language is a set of strings. One special language is  , which is the set of all possible strings generated  over the alphabet  . For example, if   =fa;b;cg then  =f;a;b;c;aa;ab;ac;ba;:::;aaaaaabbbaababa;:::g:  Namely,  is the “full” language made of characters of . Naturally, any language over  is going to be  a subset of  . Example 2.1.2 The following is a language L =fb;ba;baa;baaa;baaaa;:::g: Now, is the following a language? faa;ab;ba;g: Sure – it is not a very “interesting” language because its finite, but its definitely a language. How aboutfaa;ab;ba;;g. Is this a language? No Because; is no a valid string (which comes to demonstrate that the empty word  and; are not the same creature, and they should be treated differently. Lexicographic ordering of a set of strings is an ordering of strings that have shorter strings first, and sort the strings alphabetically within each length. Naturally, we assume that we have an order on the given alphabet.  Thus, for  =fa;bg, the Lexicographic ordering of  is ;a;b;aa;ab;ba;bb;aaa;aab;:::: Languages and set notation Most of the time it would be more useful to use set notations to define a language; that is, define a language by the property the strings in this language posses. For example, consider the following set of strings n o  L = x x2fa;bg andjxj is even : 1 In words, L is the language of all strings made out of a;b that have even length. 1 Next, consider the following set n o L = x there is a w such that xw = illinois : 2 So L is the language made out of all prefixes of L . We can write L explicitly, but its tedious. Indeed, 2 2 2 L =f;i;il;ill;illi;illin;illino;illinoi;illinoisg: 2 22= a Why should we care about languages? Consider the language L that contains all strings over  =f0; 1;:::; 9g which are prime numbers. If primes we can build a fast computer program (or an automata) that can tell us whether a string s (i.e., a number) is in L , then we decide if a number is prime or not. And this is a very useful program to have, since primes most encryption schemes currently used by computers (i.e., RSA) rely on the ability to find very large prime numbers. Let us state it explicitly: The ability to decide if a word is in a spe- cific language (like L ) is equivalent to performing a computational primes Yes task (which might be extremely non-trivial). You can think about this Program decide- Input schematically, as a program that gets as input a number (i.e., string made ingifiheinputis out of digits), and decides if it is prime or not. If the input is a prime a prime number. No number, it outputs Yes and otherwise it outputs No. See figure on the right. 2.1.4 Strings and programs An text file (i.e., source code of a program) is a long one dimensional string with specialhNLi (i.e., newline) charactersthatinstructthecomputerhowtodisplaythefileonthescreen. Thatis, thespecialhNLicharacters instruct the computer to start a new line. Thus, the text file if x=y then jump up and down and scream. Is in fact encoded on the computer as the string if␣x=y␣thenhNLi␣␣jump␣up␣and␣down␣and␣scream. Here, ␣ denote the special space character andhNLi is the new-line character. It would be sometime useful to use similar “complicated” encoding schemes, with sub-parts separated by or rather than byhNLi. Program input and output can be consider to be files. So a standard program can be taught of as a 1   function that maps strings to strings. That is P :   . Most machines in this class map input strings to two outputs: “yes” and “no”. A few automatas and most real-world machines produce more complex output. 2.2 State machines 2.2.1 A simple automata Here is a simple state machine (i.e., finite automaton) M that accepts all strings starting with a. a q q ∗ 0 1 6 q rej ∗ Here represents any possible character. Notice key pieces of this machine: three states, q is the start state (arrow coming in), q is the final 0 1 state (double circle), transition arcs. To run the machine, we start at the start state. On each input character, we follow the corresponding arc. When we run out of input characters, we answer “yes” or “no”, depending on whether we are in the final state. The language of a machine M is the set of strings it accepts, written L(M). In this case L(M) = fa;aa;ab;aaa;:::g. 1 Here, we are considering simple programs that just read some input, and print out output, without fancy windows and stuff like that. 232.2.2 Another automata (This section is optional and can be skipped in the lecture.) Here is a simple state machine (i.e., finite automaton) M that accepts all ASCII strings ending with ing. ? g i n q q q q 0 1 2 3 Notice key pieces of this machine: four states, q is the start state (arrow coming in), q is the final state 0 3 (double circle), transition arcs. To run the machine, we start at the start state. On each input character, we follow the corresponding arc. When we run out of input characters, we answer “yes” or “no”, depending on whether we are in the final state. The language of a machine M is the set of strings it accepts, written L(M). In this case L(M) = fwalking;flying;ing;:::g. 2.2.3 What automatas are good for? People use the technology of automatas in real-world applications: – Find all files containing -ing (grep) – Translate each -ing into -iG (finite-state transducer) – How often do words in Chomsky’s latest book end in -ing? 2.2.4 DFA - deterministic finite automata We will start by studying deterministic finite automata (DFA). Each node in a deterministic machine has exactly one outgoing transition for each character in the alphabet. That is, if the alphabet isfa;bg, then all nodes need to look like q 1 a q 0 b q 2 Both of the following are bad, where q =6 q and the right hand machine has no outgoing transition for 1 2 the input character b. q q 1 1 a a q q 0 0 a q 2 So our -ing detector would be redrawn as: 24not i or g not i i gg n i q q q q 0 1 2 3 i not i or n i not i 2.3 More examples of DFAs 2.3.1 Number of characters is even Input:  =f0g. Accept: all strings in which the number of characters is even. 0 q q 0 1 0 2.3.2 Number of characters is divisible by 3 Input:  =f0g. Accept: all strings in which the number of characters is divisible by 3. 0 0 q q q 0 1 2 0 2.3.3 Number of characters is divisible by 6 Input:  =f0g. Accept: all strings in which the number of characters is divisible by 6. 0 0 0 0 0 q q q q q q 0 1 2 3 4 5 0 This example is especially interesting, because we can achieve the same purpose, by observing that n mod 6 = 0 if and only if n mod 2 = 0 and n mod 3 = 0 (i.e., to be divisible by 6, a number has to be divisible by 2 and divisible by 3 a generalization of this idea is known as the Chinese remainder theorem). So, we could run the two automatas of Section 2.3.1 and Section 2.3.2 in parallel (replicating each input character to each one of the two automatas), and accept only if both automatas are in an accept state. This idea would become more useful later in the course, as it provide a building operation to construct complicated automatas from simple automatas. 252.3.4 Number of ones is even Input is a string over  =f0;1g. Accept: all strings in which the number of ones is even. 0 0 1 q q 0 1 1 2.3.5 Number of zero and ones is always within two of each other Input is a string over  =f0;1g. Accept: all strings in which the difference between the number of ones and zeros in any prefix of the string is in the range2;:::; 2. For example, the language contains , 0, 001, and 1101. You even have an extended sequence of one character e.g. 001111, but it depends what preceded it. So 111100 isn’t in the language. 1 1 1 1 q q q q q −2 −1 0 1 2 0 0 0 0 0 0,1 1 q rej Notice that the names of the states reflect their role in the computation. When you come to analyze these machines formally, good names for states often makes your life much easier. BTW, the language of this DFA is n o  L(M) = w w2f0;1g and for every x that is a prefix of w;j1(x) 0(x)j 2 : 2.3.6 More complex language The input is strings over  =f0;1g. Accept: all strings of the form 00w, where w contains an even number of ones. 0 0 1 0 0 A B C D 1 1 1 q rej 0,1 You can name states anything you want. Names of the formq are often convenient, because they remind X you of what’s a state. And people often make the initial state q . But this isn’t obligatory. 0 262.4 The pieces of a DFA To specify a DFA (deterministic finite automata), we need to describe – a (finite) alphabet – a (finite) set of states – which state is the start state? – which states are the final states? – what is the transition from each state, on each input character? 27Chapter 3 Lecture 3: More on DFAs 27 January 2009 This lecture continues with material from section 1.1 of Sipser. 3.1 JFLAP demo Go to http://www.jflap.org. Run the applet (“Try applet” near the bottom of the menu on the lefthand side). Construct some small DFA and run a few concrete examples through it. 3.2 Some special DFAs  For  =fa;bg, consider the following DFA that accepts  : a,b S The DFA that accepts nothing, is just a,b S 3.3 Formal definition of a DFA Consider the following automata, that we saw in the previous lecture: 0 q q 0 1 0 We saw last class that the following components are needed to specify a DFA: (i) a (finite) alphabet (ii) a (finite) set of states (iii) which state is the start state? (iv) which states are the final states? (v) what is the transition from each state, on each input character? 28Formally, a deterministic finite automaton is a 5-tuple (Q; ;;q ;F ) where 0  Q: A finite set (the set of states).  : A finite set (the alphabet)   :Q Q is the transition function.  q : The start state (belongs to Q). 0  F: The set of accepting (or final) states, where FQ. For example, let  =fa;bg and consider the following DFA M, whose language L(M) contains strings consisting of one or more a’s followed by one or more b’s. a b a b q q q 0 1 2 b a q rej a,b Then M = (Q; ;;q ;F ), Q =fq ;q ;q ;q g, and F =fqg. The transition function  is defined by 0 0 1 2 rej 2  a b q q q 0 1 rej q q q 1 1 2 q q q 2 rej 2 q q q rej rej rej We can also define  using a formula (q ;a) =q 0 1 (q ;a) =q 1 1 (q ;b) =q 1 2 (q ;b) =q 2 2 (q;t) =q for all other values of q and t. rej Tables and state diagrams are most useful for small automata. Formulas are helpful for summarizing a group of transitions that fit a common pattern. They are also helpful for describing algorithms that modify automatas. 3.4 Formal definition of acceptance We’ve also seen informally how to run a DFA. Let us turn that into a formal definition. Suppose M =  (Q; ;;q ;F ) is a given DFA and w = w w :::w 2  is the input string. Then M accepts w iff there 0 1 2 k exists a sequence of states r ;r ;:::r in Q, such that 0 1 k 1. r =q 0 0 2. (r ;w ) =r for i = 0;:::;k 1. i i+1 i+1 3. r 2F. k 29 n o The language recognized by M, denoted by L(M), is the set w M accepts w . For example, when our automaton above accepts the string aabb, it uses the state sequence q q q q q . 0 1 1 2 2 (Draw a picture of the transitions.) That is r =q , r =q , r =q , r =q , and r =q . 0 0 1 1 2 1 3 2 4 2 Note that the states do not have to occur in numerical order in this sequence, e.g. the following DFA accepts aaa using the state sequence q q q q . 0 1 0 1 a q q 0 1 a A language (i.e. set of strings) is regular if it is recognized by some DFA. 3.5 Closure properties Consider the set of odd integers. If we multiply two odd integers, the answer is always odd. So the set of odd integers is said to be closed under multiplication. But it is not closed under addition. For example, 3 + 5 = 8 which is not odd. To talk about closure, you need two sets: a larger universe U and a smaller set X U. The universe is often supposed to be understood from context. Suppose you have a function F that maps values in U to values in U. Then X is closed under f if F applied to values from X always produces an output value that is also in X. For automata theory, U is usually the set of all languages and X contains languages recognized by some specific sort of machine, e.g. regular languages. 3.5.1 Closure under complement of regular languages Here we are interested in the question of whether the regular languages are closed under set complement. (The complement language keeps the same alphabet.) That is, if we have a DFA M = (Q; ;;q ;F ) 0 0  accepting some language L, can we construct a new DFA M accepting L =  nL? Consider the automata M from above, where L is the set of all strings of at least one a followed by at least one b. a b a b q q q 0 1 2 b a q rej a,b The complement language L contains the empty string, strings in which some b’s precede some a’s, and strings that contain only a’s or only b’s. 0 0 Our new DFA M should accept exactly those strings that M rejects. So we can make M by swapping final/non-final markings on the states: 30a b a b q q q 0 1 2 b a q a,b rej 0 Formally, M = (Q; ;;q ;QnF ). 0 3.6 Closure under intersection We saw in previous lecture an automatas that accepts strings of even length, or that their length is a product of 3. Here are their automatas: a a a q q q q q 0 1 0 1 2 a a M : M : 1 2 Assume, that we would like to build an automata that accepts the language which is the intersection of the language of both automatas. That is, we would like to accept the language L(M )\L(M ). How do we 1 2 build an automata for that? The idea is to build a product automata of both automatas. See the following for an example. a q q 0 1 a p 0 (q ,p ) (q ,p ) 0 0 1 0 a a a a a p 1 (q ,p ) (q ,p ) q 0 1 1 1 a a a p 2 (q ,p ) (q ,p ) 0 2 1 2 0 0 0 0 0 0 Given two automatas M = (Q; ;;q ;F ) and M = (Q; ;;q ;F ), their product automata is the 0 0 0 automata formed by the product of the states. Thus, a state in the resulting automata N = MM is a 0 0 0 pair (q;q ), where q2Q and q 2Q . 310 The key invariant of the product automata is that after reading a word w, its in the state (q;q ), where, 0 0 q is that state that M is at after reading w, and q is the state that M is in after reading w. 0 As such, the intersection language L(M)\L(M ) is recognized by the product automata, where we set 0 0 0 the pairs (q;q )2Q(N) to be an accepting state for N, if q2F and q 2F . 0 Similarly, the automata accepting the union L(M)L(M ) is created from the product automata, by 0 0 0 setting the accepting states to be all pairs (q;q ), such that either q2F or q 2F . As such, the automata accepting the union language L(M )L(M ) is the following. 1 2 a q q 0 1 a a p 0 (q ,p ) (q ,p ) 0 0 1 0 a a a a p 1 (q ,p ) (q ,p ) q 0 1 1 1 a a a p (q ,p ) (q ,p ) 2 0 2 1 2 3.7 (Optional) Finite-state Transducers Inmanyapplications, transitionsalsoperformactions. E.g. atransitionreading WANNATALKfromthenetwork might also call some C code that opens a new HTTP connection. Finite-state transducers are a simple case of this. An FST is like a DFA but each transition optionally writes an output symbol. These can be used to translate strings from one alphabet to another. For example, the following FST translates binary numbers into base-4 numbers. E.g. 011110 becomes 132. We’ll assume that FSTs don’t accept or reject strings, just translate them. 1/ǫ q q 0 1 0/2,1/3 0/ǫ 1/1,0/0 q 2 So, formally, an FST is a 5-tuple (Q; ; ;;q ), where 0 – Q is a finite set (the states). –  and are finite sets (the input and output alphabets). –  :Q Q is the transition function.  – q is the start state 0 32Notation: = fg .  The transition table for our example FST might look like the following.  0 1 q (q ;) (q ;) 0 1 2 q (q ; 0) (q ; 1) 1 0 0 q (q ; 2) (q ; 3) 2 0 0 33Chapter 4 Lecture 4: Regular Expressions and Product Construction 29 January 2009 This lecture finishes section 1.1 of Sipser and also covers the start of 1.3. 4.1 Product Construction 4.1.1 Product Construction: Example    Let  =fa;bg and L is the set of strings in  that have the form a b and have even length. L is the    intersection of two regular languagesL = a b andL = () . We can show they are regular by exhibiting 1 2 DFAs that recognize them. r 0 a,b a b a,b a,b b a r q q 1 0 1 drain L L 1 2 We can run these two DFAs together, by creating states that remember the states of both machines. (q ,r ) (q ,r ) (drain,r ) 0 0 1 0 0 a a b a a a,b a,b b b b (q ,r ) (q ,r ) (drain,r ) 0 1 1 1 1 Notice that the final states of the new DFA are the states (q;r) whereq is final in the first DFA and r is final in the second DFA. To recognize the union of the two languages, rather than the intersection, we mark all the states (q;r) such that either q or r are accepting states in the their respective DFAs. 34State of a DFA after reading a word w. In the following, given a DFA M = (Q; ;;q ;F ) , we will 0  be interested in what state the DFA M is in, after reading the characters of a string w =w w :::w 2  . 1 2 k As in the definition of acceptance, we can just define the sequence of states that M would go through as it reads w. Formally, r =q , and 0 0 r =(r ;w ); for i = 1;:::;k: i i1 i As such, r is the state M would be after reading the string w. We will denote this state by (q ;w). Note, k 0 that by definition   (q ;w) = (q ;w :::w ); w : 0 0 1 k1 k In general, if the DFA is in a state q, and we want to know in what state it would be after reading a string w, we will denote it by (q;w). 4.2 Product Construction: Formal construction 0 0 0 0 0 We are given two DFAs M = (Q; ;;q ;F ) and M = (Q; ;;q ;F ) both working above the same 0 0 alphabet . Their product automata is the automata   0 N = Q; ;  ; (q ;q ); F ; N 0 N 0 0 0 0 whereQ =QQ , and  :Q Q. Here, for q2Q, q 2Q and c2 , we define N   0 0 0  ( (q;q ) ;c ) = (q;c);  (q;c) : (4.1) N z state of N The set F Q of accepting states is free to be whatever we need it to be, depending on what we want N 0 N to recognize. For example, if we would like N to accept the intersection L(M)\L(M ) then we will set 0 0 0 0 F =FF . If we wantN to recognize the union languageL(M)L(M ) thenF =(FQ )(QF ). N N  Lemma 4.2.1 For any input word w2  , the product automata N of the DFAs M = (Q; ;;q ;F ) and 0 0 0 0 0 0 0 M = (Q; ;;q ;F ), is in state (q;q ) after reading w, if and only if (i) M in the state q after reading w, 0 0 0 and (ii) M is in the state q after reading w. Proof: The proof is by induction on the length of the word w. 0 0 If w = is the empty word, then N is initially in the state (q ;q ) by construction, where q (resp. q ) 0 0 0 0 0 is the initial state of M (resp. M ). As such, the claim holds in this case. Otherwise, assumew =w w :::w w , and the claim is true by induction for all input words of length 1 2 k1 k strictly smaller than k. 0 Let (q ;q ) be the state that N is in after reading the string wb = w :::w . By induction, as k1 1 k1 k1 0 0 jwbj =k 1, we know that M is in the state q after reading wb, and M is in the state q after reading k1 k1 wb. Let q =(q ;w ) =((q ;wb); w ) =(q ;w) and k k1 k 0 k 0 0 0 0 0 0 0 0 0 q = (q ;w ) = ( (q ;wb); w ) = (q ;w): k k k k1 0 0 0 0 As such, by definition, M (resp. M ) would in the state q (resp. q ) after reading w. k k Also, by the definition of its transition function, after reading w the DFA N would be in the state  0 0 0  ((q ;q );w) = ( ((q ;q );wb);w ) = (q ;q ); w N 0 N N 0 k N k1 k 0 0 k1  0 0 = (q ;w ); (q ;w ) =(q ; q ); k1 k k k k1 k see Eq. (4.1). This establishes the claim. 0 0 0 0 0 Lemma 4.2.2 Let M = (Q; ;;q ;F ) and M = (Q; ;;q ;F ) be two given DFAs. Let N be their 0 0 0 0 produced automata, where its set of accepting states is FF . Then L(N) =L(M)\L(M ). 35

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.