Automata and Complexity
Automata and Complexity CS 4510
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4510 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/234141/cs-4510-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Automata and Complexity
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Turing Machine Computation History Veri cation by a PDA Let A Q 21quot6M 15 1a 1T be a deterministic Turing machine and 11 be an input to A Let A Q U P U Given a string UV E Aquot design a PDA that accepts iff V is not a valid immediate successor configuration of U on input 11 Let P be a PDA for this verification problem If U or V is not a valid configuration of A on 11 then P accepts A DEA can be used to test that a string U or V is not a valid configurations of M on 11 Suppose U and V are valid configurations Let U mug ur and V 171172175 For i 3 1 consider the 2 x 3 windows Call such a window the critical window if 14741 is the state symbol in U 1 U2 If in is the state symbol in D then the first 2 x 2 window l is called the critical window Note that 171 12 there is only one critical window The description of the PDA P below uses a procedure COMPARE that accepts iff Ciw rcmtSymbol 7 177 The procedure COMPARE is described later We will assume that the stack has a bottom marker say Z STEP 1 Let m E Q RV V head is pointing to the first symbol of the tape of A The first 2 X 2 window is the critical window 1 i Let 6M 14142 pa L The correct critical window is l H 2 Handle the Right and the Stationary moves similarly Nondeterministically do one of the following two actions 1 Cm rcmtSymbol COMPARECiw mntSyiibr11 1 2 Push p onto the Stack Nondeterministically do one of the following two actions a Ciw rcmtSymbol a COMPARECiw mntSyiibr11 2 b Push a onto the Stack i Go to Step 3 to process the postcriticalwindow part of STEP 2 Let m 63 Q RW head is not pointing to the first symbol of the tape of M Processing takes place in three stagesa precriticalwindow b criticalwindow and c postcriticalwindow i 1 STEP 21 prencriticalwindow stage REPEAT long 1M1 Q Q prencriticalwindow stage Nondeterministically do one of the following two actions 1 Ciw rcmtSymbol m COMPARECm mntSyiibol 2 Push Cw rcmtSymbol onto the stack i i 1 Simulating an NTM machine by a DTM Theorem Every tn time 1 tape NTM has an equivalent 200 time 1 tape DTM N be a 1 tape NTM 6N its transition function Assume two or zero transitions from each con guration Order the two transitions as the rst and the second On input w7 a 3 tape DTM D simulates N as described below Tape 1 of D the input w Tape 3 of D a bit string that describes a path of N7s computation tree Tape 2 of D contents of N7s tape along the computation path described by the address on Tape 3 H F 9 7 U Simulating an NTM by a DTM Tape3 0 Set RejectedSoFar to TRUE Tape 1 Tape 2 CurrentState start state of N Simulate N on w guided by the contents of Tape 3 a Repeat until all the bits on Tape 3 are read 6N not de ned for CurrentState and symbol go to step 5 SN is de ned for CurrentState and symbol update CurrentState and Tape 2 if current address bit is 0 l7 use the rst second transition move right one position on Tape 3 b CurrentState is Accepting state of N HALT and ACCEPT c CurrentState is Rejecting state of N go to step 5 d Current state is neither RejectedSoFar FALSE go to step5 IF Tape 3 contains all 17s THEN IF RejectedSofar is TRUE THEN HALT and REJECT ELSE Tape 3 lt next string go to step 2 ELSE Tape 3 lt next string go to step 3 Simulating an N73 machine by a polynomial time veri er N be a 1 tape N73 machine 6N its transition function Assume Two or zero transitions from each con guration Every computation path has same length It Order the two transitions as the rst and the second Let tn be the running time of N Let w be the input on tape 1 and let 0 be a string of length Kiwi on tape 2 of the veri er V The veri er treats c as the description of an accepting path in the computation tree of N on w The veri er V simulates N as described below 1 CurrentState 9 start state of N 2 Simulate N on w guided by the contents of Tape 2 a Repeat until all the bits of c are read IF 6N is not de ned for the current state and symbol THEN HALT and REJECT ELSE 6N is de ned for the current state and symbol IF the current bit of c is 0 THEN pick the rst transition to set the current state and to modify contents of Tape 2 IF the current bit of c is 1 THEN pick the second transition to set the current state and to modify contents of Tape 2 Point to the next bit of c on ProoiTape b IF the current state is the Accepting state of N THEN HALT and ACCEPT C IF the current state is the Rejecting state of N THEN HALT and REJECT Reductions Let A and B be languages over the same alphabet E An algorithm that transforms 0 Strings in A to strings in B 0 Strings not in A to strings not in B B is decidable i A is decidable A is undecidable i B is undecidable One way to show a problem B to be undecidable is to reduce an undecidable problem A to B Reductions A Turing machine M computes a function f if M halts on all inputs On input x it writes f on the tape and halts Such a function f is called a computable function Examples increment addition multiplication shift Any algorithm with output is computing a function Reductions Let A and B be languages over 2 A is reducible to B if and only if 0 there exists a computable function f 2 a 2 such that oforallw 6 Sim E A gt fw E B Notation A gm B FACT A gm B a Z gm P w E A gt fw E Bis equivalent tow Z A gt fw Z B Reductions To Re iterate 1 Construction fw from w by an algorithm 2 Correctness w E A gt fw E B An Example involving DFAS EQDFA AB AB are DFAs and LA LB EDFA A A is a DFA and LA 0 A reduction machine on input AB two DFAs 1 Constructs the DFA A such that LA L 2 Constructs the DFA B such that LB 3 Constructs the DFA M1 such that LM1 LA LB 4 Constructs the DFA M2 such that LM2 LA LB 5 Constructs the DFA C such that LC LM1 U LM2 6 Outputs 0 Correctness 0 Suppose LA LB Then7 LC Q 0 Suppose LA 31 LB Then7 LC 31 0 That is7 EQDFA Sm EDFA An Example involving CFGS ALLOFG G l G is a CFG and LG 2 EQCFG G7H GH are CFGs and LG A reduction machine on input G a context free grammar with alphabet E l Constructs a CFC H with rules of the form 5 H 187 for all a E E 2 Outputs G7 LH 2 Correctness 0 Suppose G accepts 2 Then7 LG 0 Suppose G does not accept some string Then LG 31 That is ALLOFG gm EQcpg The Halting problem HALTTM M7w l M is a DTM and M halts on w The reduction machine outputs a DTM that loops whenever M reaches the rejecting state On input M7 w 1 Constructs the following machine M Read input x Simulate M on x If M accepts7 halt and accept If M halts and rejects7 enter a loop 2 Outputs M 7w That is ATM Sm HALTTM is undecidable since ATM is undecidable The Halting problem Three machines 0 A reduction machine that is a DTM 0 Input to the reduction machine is M711 where M is a DTM 0 Output of the reduction machine is M w7 where M is a DTM The Halting problem The output DTM M has the input M hard coded into it Let M QyEyFydqsquqr What is M M Q7 27 P7 67 197 gm 17 Q Q U gl7QT De ne 6 as follows For all states p7 for all states q 31 qr7 for all symbols a7b7 for all D E LR7 S if 5197 0 Q7 57 D then MP7 0 1750 For all states p7 for all symbols a7b7 for all D E LR7 S if 61 1 qhb7 D then 6 pa q17b75 For all symbols 17 include the transition 6 qla q17a78 M is constructed from M by the reduction machine ETM M MisaTM and LM y A reduction machine on input Mw 1 Constructs the following machine M Read input x If x 31 w then reject If x w7 Simulate M on w If M accepts7 halt and accept 2 Outputs M Correctness o If M accepts w then LM is not empty o If M does not accept w then LM is empty That is ATM Sm ETM E TM MMisaTMandLM ye ATM Sm This implies that m is undecidable This in turn implies that ETM is undecidable At least one of them must be not recognizable m is recognizable ETM is not recognizable EQTM M1M2 M1 and M2 are TMs and LM1 LltMg EQTM is undecidable Is EQTM recognizable See the text book Language is Contextfree CONTEXT 7 FREETM M l M is a TM and LM is context 7 free A reduction machine on input M7 w 1 Constructs the following machine M Read input x If x has the form 0 1 2 then halt and accept If x is not of this form7 simulate M on w If M accepts7 halt and accept 2 Outputs M Correctness o LM is 2 if M accepts w o LM is not context free if M does not accept w ATM Sm CONTEXT 7 FREETM CONTEXT 7 FREETM is undecidable since ATM is undecidable Language is Not Regular REGULARTM M l M is a TM and LM is NOT regular A reduction machine on input M7 w 1 Constructs the following machine M Read input x If x is not of the form OH then halt and reject If x is of this form7 simulate M on w If M accepts7 halt and accept 2 Outputs M Correctness o LM is Q if M does not accept w o LM is not regular if M accepts w ATM Sm REGULARTM REGULARTM is undecidable since ATM is undecidable Not Recognizable REGULARTM is not recognizable REGULARTM is not recognizable Post Correspondence Problem Example Here is an instance M w of ATM 0 input string w 0100 0 machine M has set of states Q q0 q1q2 q7 gm 0 machine M has start state go 6 Q and accept state gm 6 Q 0 machine M has tape alphabet P 0 1 2 3 U 0 machine M has transition function 6 A few of the transitions of M are 50070 077271307 561771 6127307 561270 270713 0 machine M cleans up after itself if it reaches state qa it cleans the tape and sits at the rst tape square Observation The con gurations of M on w are 00 q001oo 01 2q7100 Cg 23q200 Cg 230an C4 2301a C5 2318 06 2C1a C7 Cla Hence the accepting computation history of M on w is q001002q710023q200230qa0230qa23qaanqa Nondeterministic Finite Automata w i the second bit from last is 1 On input w ule 10 an NFA does Repeat until end of input Current bit is 1 GUESS if it is the second last bit guess YES read the next bit and accept guess NO Nondeterministic Pushdown Automata 953 l 96 7g 1 IHPUti 1M 39 39 xmy1y2 39 39 ym Repeat until end of input GUESS if current input position is the check position in x guess NO Read current symbol The input head moves to next position If this symbol is reject push X onto the stack guess YES Read current symbol If this symbol is reject Otherwise store this symbol in the state Read and ignore until If no reject Until stack empty read from input and pop from stack lf current symbol different from stored symbol accept ignoring input until the end else reject Reject A Nondeterministic algorithm for gtllt of a decidable language Let L be a decidable language accepted by a decider DTM M w E L iff 3 k and 3 a partition of w wl wk such that wi E LV 12k A NTM decider M accepts L as follows GUESS the positions 21 z39k where w is chopped Traverse the input from the left end at each position M GUESS whether or not to mark the symbol Simulate M on each piece of w one after the other Accept iff all the pieces are accepted by M Input W A Nondeterministic algorithm for compositeness w1w2 wn an 71 bit number with W 2 2 Problem Accept iff W is composite A two tape NTM decides if W is composite as follows Tape 1 contains the input W H F 9 7 U 03 00 lf W 2 then reject GUESS a number X and write it on tape 2 Until the end of the input do Nondeterministically write 01 on tape 2 move right by one position on the input tape and tape 2 le S 1reject Write a separator at the right most end of tape 2 Go to the left most position of the input tape GUESS a number Y and write on tape 2 after X Until the end of the input do Nondeterministically write 01 on tape 2 move right by one position on the input tape and tape 2 lfY lt 1reject lf XY W accept else reject Path nding in a Graph Given a directed graph G V E where V 12 n Problem Decide if there is a directed path from vertex 1 to vertex n Assume input is the adjacency matrix A for G Az j 1 if 27 6 E 0 otherwise Compute NameLength ogz Let CurrentVertm H 1 Let EdgesSeen H 0 Repeat until EdgesSeen n GUESS a vertex Nez ertez guess a 01 binary number of length NameLength If ACurrentVertm Nethertez 0 HALT and REJECT If Nm ertm n HALT and ACCEPT CurrentVertm H Nethertez Increment EdgesSeen HALT and REJECT Finding a KClique in a Graph Given a directed graph G V E where V 12 n and an integer K with 1 S K S 71 Problem Decide if there is a complete graph of size K in G Assume graph G is given as an adjacency matrix A Az jl 1 if 27 6 E 0 otherwise Compute NameLength Tlogz Copy K to Tape 2 Repeat until Tape 2 is 0 Write a separator mark on Tape 3 GUESS a vertex u and write it on Tape 3 guess a 01 bit number with length NameLength Decrement number in Tape 2 Repeat until no more vertices in Tape 3 Read the rst vertex from Tape 3 and store it in CurrentVertex Delete the rst vertex from Tape 3 For all vertices u in Tape 3 do If ACurrentV rtexu 0 halt and reject Halt and accept