### Create a StudySoup account

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

Already have a StudySoup account? Login here

# COMPUTATIONAL STRUCTURES CS 311

PSU

GPA 3.91

### View Full Document

## 5

## 0

## Popular in Course

## Popular in ComputerScienence

This 221 page Class Notes was uploaded by Orrin Rutherford on Wednesday September 2, 2015. The Class Notes belongs to CS 311 at Portland State University taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/168290/cs-311-portland-state-university in ComputerScienence at Portland State University.

## Popular in ComputerScienence

## Reviews for COMPUTATIONAL STRUCTURES

### What is Karma?

#### Karma is the currency of StudySoup.

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

Date Created: 09/02/15

08311 Computational Structures Turing machines and other models of computation Lecture I5 epor antgggm 39 Recognizable vs Decidable A language L is Turing recognizable if some Turing machine recognizes it gt Some strings not in L may cause the TM to loop gt Turing recognizable recursively enumerable A language L is Turing decidable if some Turing machine decides it gt To decide is to return a definitive answer the TM must halt on all inputs gt Turing decidable decidable recursive ca Portlanme Decidable Language A1 OZnin Z Decidable by M1 1 Sweep right counting Os and crossing off every other 0 2 if in 1 there was a single 0 accept 3 otherwise if in 1 there was an odd number of Os halt 4 return the head to the left and repeat from 1 epor anm 3 in State Reading Wme Move New State I 0 k R 0 State diagram 0 o o R 7 1 k L 4 1 0 0 R 2 for M1 1 X X R 1 2 k R 9 2 0 gtlt R 1 7 x x p 7 4 k R 0 4 0 0 L 4 4 gtlt gtlt L 4 State 0 I m looking at first input 7 4 4 L h symbol 7 o gtlt R 1 7 gtlt gtlt R 7 State 7 I ve seen exactly one 0 0 on this pass State 1 I ve seen an even number of 0s on this pass State 2 I ve seen an odd number of 0s on this pass State 4 I m skipping back to the start Portland State Variations on TMs Machines that can only go L or R but not 8 Machines with a explicit Reject state Multihead Turing machines Multitape Turing machines Nondeterministic Turing machines None of these variations change the power of the machine can Portlanme Determinism doesn t matter How to prove this gt Simulate a nondeterministic Turning machine by a deterministic Turing machine gt DTM has to run each of the NTM computations in turn until it finds one that accepts or it has tried them all What s the problem gt One of the NTMs may run for ever What s the solution epor anm 7 Elaborating some Definitions Configuration gt Tape Contents nonblank gt State gt Head position Representation uqv gt Tape Contentsuv gt Stateq gt Head position reading first leftmost symbol ofv epor anm 8 Recall In manual execution of TM last lecture we wrote a sequence of configurations When can one configuration follow another Call this the yields relation can Portlanme Special configurations Start configuration of M on x gt A configuration with start state of M to the left on x Accepting Configuration of M gt A configuration containing the halt state of M Rejecting Configuration of M gt A configuration not containing the halt state that has no successor configurations by the yields relation for M Halting Configuration eitherAccepting or Rejecting e Portlanme 390 Basic definitions Deterministic TM gt The moves are all functionally determined by the state and symbol at the tape head 0 Nondeterministic TM gt The moves are a general relation with potentially multiple applicable moves 0 In both cases the set of all moves is finite e Portlanme quot Deterministic AcceptReject The deterministic machine M accepts x if gt There is a series of configurations 0 that begins with a start configuration for M on x o is related by the yields relation for M 0 ends with an accepting configuration for M The deterministic machine M rejects x if gt There is a series of configurations 0 ends with a rejecting configuration for M e Portlanme 392 Nondeterministic Accept and Reject The nondeterministic machine accepts if there is some sequence of configurations that leads to an accepting configuration The nondeterministic machine rejects if all possible sequences of configurations lead to a rejecting configuration can Portlanme 393 Trees of Computations The nondeterministic computation can be viewed as a tree or possible computations gt Nodes are configurations gt The daughters of a configuration are all configurations reachable in one step by yields This is a finitely branching tree gt What does the tree look like for our composite number program gt Can we order the alternatives can Portlanme 394 Simulation Strategy To simulate the NTM construct a DTM that will search this tree of possible NTM computations What kind of search strategy should we use How can we express that strategy can Portlanme 395 Tree addresses An ordered tree with fanout bounded by k can be addressed by strings over the alphabet O k1 What ordering on strings reflects a breadth first search strategy can Portlanme 396 Construction Use a 3 tape DTM to simulate the NTM gt Tape 1 contains the input and is never changed gt Tape 2 contains the tree address gt Tape 3 is the simulation tape Initialize the tree address to empty string gt At each stage 0 Copy the input tape to the simulation tape 0 Simulate the NTM branch described by address tape 0 Accept if NTM accepts 0 Otherwise increment tree address next string in lexicographic order can Portlanme I7 Correctness If NTM accepts x will DTM accept x o If DTM accepts x will NTM accept x e Portlansm t Rejection As constructed we never reject When can we reject e Portlanm Universal Turing Machines A universal Turing Machine 1 takes as input a description of some other Turning machine M and 2 an input string w and 3 simulates the action of M running on w 4 halting looping or accepting as does M e Portlanme 2 How to build a Universal TM Remember a Universal TM U must still have only a fixed and finite set of states a finite alphabet and therefore a finite set of instructions 8 Relabel the TM that we are simulating S to use states from Nat and symbols from ai i 6 Nat gt That s OK there are bound to be enough gt Pick a fixed alphabet for U say I u 01 gt Encode the instructions of S in Th e Portlanme 2 Let U have three tapes tape 1 stores the encoding of S tape 2 stores the input string tape 3 records the state of S encoded in FL U does the following Writes the start state on tape 3 o If the state on tape 3 is a final state then halt otherwise read the current symbol from tape 2 and find the instruction on tape 1 that applies 0 Write the new state onto tape 3 and perform the indicated write and move operations on tape 2 e Portlanme 22 Why are UTMs important They capture the idea of a storedprogram computer gt First storedprogram computer Manchester Baby was built in 1948 gt Earlier computers Harvard Mk I and ENIAC were fixed program computers The idea of a computer that can take another computer as input is key to proofs of undecidability and unsolvability can Portlanme 23 What is Computation What does computable mean gt A computer can calculate it gt There is some formally described execution process and a formally described set of instructions an algorithm that describes how to get the answer epor anlglare 24 Examples Generating strings from a grammars gt derivation is the process the algorithm is encoded in the rules of the grammar Accepting a string in a state machine gt Executing an ML program gt These are all Models of Computation e Portlanme 25 The Power of Model We know that some models of computation are more powerful than others gt CFG are more powerful than Regular Grammars gt DFAs have the same power as NFAs gt Turing machines are more powerful than PDAs Is there a most powerful model can Portlanme 26 Turing s Thesis Our intuitive notion of computation is precisely captured by the formal device known as a Turing Machine There is no model of computation more powerful than a Turing machine Why is this a thesis and not a theorem e Portlanme 27 Steampowered Turing machine Sieg Hall I987 What about Alonzo Church o The Turing thesis is usually called the ChurchTuring r Thesis in honor of Alonzo Church 1903 1995 gt Working with his students J Barkley Rosser Steven C Kleene and Alan M Turing Church established the equivalence of the Lambda calculus recursive function theory and Turing machines gt They all capture the notion of computability Portland ats Other Notions of Computability Simple a programming language with while loops Recursive Functions Lambda calculus MarkovAlgorithms Post Algorithms Post Canonical Systems Portlanmete 3 Simple Hein p 776 A Simple program is defined as follows 1 V an infinite set of variables that take values in Nato and are initially O 2 S statements which are either 21 While statements while V O do 8 0d 22 Assignments V 0 V1 succV2 V1 predV2 or 23 a sequence of statements separated by 3 S is a simple program can Portlanme 339 Note that pred0 O to ensure that we stay in Nato Can we compute anything interesting with this language 0 yes 32 can Portlan9i tet9 Macro Statement Simple Code for Macro XY X suCCY X predX X3 X 0 X suCCX X suCCX X suCCX XXY I Y while 175 0 do X suCCX I pred od Loop Forever X 0 X suCCX while X73 0 do Y2 0 od repeat S until X 0 S while X73 0 do Sod Figure 132 Some simple macros Let s try x y xlty while xlty do 8 od 49 Portlansl tgte 33 Markov Algorithms A Markov Algorithm over an alphabet A is a finite ordered sequence of productions x gty where x y e A Some productions may be Halt productions gt eg abc gt b ba gt x halt Execution proceeds as follows 49 Portlanme 34 1 Let the input string be w 2 The productions are scanned in sequence looking for a production x gt y where x is a substring of w 3 the leftmost x in w is replaced by y 4 If the production is a halt production we halt 5 If no matching production is found the process halts 6 If a replacement was made we repeat from step 2 e Portlanme 35 Note that a production A gt a inserts a at the start of the string What does this Markov algorithm do aba gtb ba gtb b gta e Portlanm 36 Example Proof using the Pumping Lemma for Regular Languages Andrew P Black 22 April 2008 Prove that the language E w E 01 w has an equal number of Os and ls is not regular Proof We prove the required result by contradiction So7 we assume that E is regular Then7 by the pumping lemma7 there is a pumping length p such that all strings s in E of length p or more can be written as s myz where 1 3473A 2 izyigmnd 3 zyiz E E7 for all i 2 0 Consider the string 3 01 11 Clearly7 p E E and lsl 2 197 so we should be able to nd a decomposition of s into myz that meets conditions 173 above How about z z A7 y 01 11 This meets conditions 1 and 3 But no7 it fails to meet condition 2 If l my l g 197 then my must contain just 0s and no 1s Hence7 y must contain just 0s and no 1s So7 if s myz E E7 it follows that 2 E7 since m2 has fewer 0s than myz but the same number of 1s Thus7 we have found a string in E that cannot be pumped7 which contradicts the assumption that E is regular D Note that we get to choose a string 3 to suit our purposes If7 instead7 we had chosen 017 then we would not have been able to complete the proof Why not Because that particular string can be pumped But this is not a problem the lemma says that all strings can be pumped7 so all that we need do is nd one string that cannot be pumped7 and we have the contradiction that we are looking for What is the minimum pumping length for the language L 0001 The minimum pumping length for a language L is the smallest p such that all strings of length p or more can be pumped In L 0001 1 000 can t be pumped because 0000 is not in L 2 0001 can be pumped put z 0007 y 17 z A So the minimum pumping length is 4 How many states would you expect to nd in a DFA recognizing L CS3 I Computational Structures Topdown parsing with a Parse Table Lecture II a Portlana tgm Recall the theory whereSis the grammar39s push S start symbol A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or 2 replace A on the stack with a where A gtoo is a rule of the grammar derive eporaansiaem 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or 2 replace A on the stack with a where A gtoo is a rule of the grammar derive How to choose which A gtoo Portlangin Etkasilt 2 Recall the Practice and moreConcat C if couldBeSimple lookahead then let val x closureC val y moreConcatC in case y of NONE gt SOME X moreConcat a closure moreConcat A SOME 2 gt SOMECConcathz end else NONE and couldBeSimple LeFtParen true couldBeSimple Hash true couldBeSimple Zero true couldBeSimple Single true couldBeSimple False Portlangin tate ERSITY Topdown predictive parsers Use an explicit stack instead of recursion Represent the transitions of the PDA in a table rather than as code Choice of action of the parser which production to use to expend the stack symbol represented by three functions Nullable First Follow 0 Nullable Can a symbol derive the empty string False for every terminal symbol Nullable term or nonterm gt bool 0 First all the terminals that a nonterminal could possibly derive as its first symbol First term or nonterm gt set term First sequenoeterm nonterm gt set term 0 Follow all the terminals that could immediately follow the string derived from a nonterminal Follow nonterm gt set term can Portlan sgm Example First and Follow Sets E gt T E E gt T E I First E quotquot quotidquot Follow E quotquotquotquot E A A First F quotquot quotidquot Follow F quotquotquotquot quotquot T gt F T FirstT quotquot quotidquot FollowT quotquotquotquotquotquot First E quotquot A Follow E39 quotquotquotquot A T F T First T39 quotquot A Follow T39 quotquotquotquotquotquot T gt A F 39 E a First of a terminal is itself F gt i d 0 First can be extended to be defined on a sequence of symbols Nullable if is in Firstsymbol then that symbol is nullabe Sometimes rather than let be a symbol we use an additional function Nullable gt Nullable E39 true gt NullableT39 true gt Nullable for all other symbols is false E gtTE39 E39 gt TE39 E39 gt T gtFT39 T39 gtFT39 T39 gt F gt E F gtid 7 Computing FIRST 0 Use the following rules until no more terminals can be added to any FIRST set 1 if X is a terminal FIRSTX X 2 if X gt A is a production then add A to FIRSTX or set nullable of X to true 3 if X is a nonterminal and X gt Y1 Y2 Yk add a to FIRSTX if a in FIRSTY and for all jlt i nullable Yj equivalently A in FlRSTY eg if Y1 can derive A then if a is in FIRSTY2 a is surely in FIRSTX as well Example First Computation 0 Terminals 5 g First First First 3 FAT 0 Empty Productions E A add A to FirstE39 add A to FirstT39 E i if 0 Other NonTerminaIs Computing from the lowest layer F up FirstF id FirstT39 A FirstT FirstF id FirstE39 A FirstE FirstT id 3333 Computing FOLLOW 0 Use the following rules until nothing can be added to any follow set 1 Place the end of input marker in FOLLOWS where S is the start symbol This is Hein s rule 1 2 If A gt a B b then put everything in FlRSTb except A into FOLLOWB This is Hein s rule 3 3 If there is a production A gt a B orA gt a B b where FlRSTb contains A Le nullable b then put everything in FOLLOWA into FOLLOWB This is a combination ofHein s rules 2 amp 4 Example Follow Computation 0 Rule 1 Start symbol Add to FollowE 0 Rule 2 Productions with embedded nonterminals Add First to FollowE Add First to FollowE Add FirstE39 A to FollowT E gt T E39 Add FirstT39 A to FollowF E39 gt T E39 0 Rule 3 Nonterminal in rightmost position E 9T Add followE39 to followE39 doesn t do much T39 F T39 Add follow T to followT39 T39 gt A Add followT to followF since T39 gtA E gt 1 E gt I Add followT39 to followF since T39 gt A Table from First and Follow For each production A gt to do steps 1 3 below 1 For each terminal a in First to add A gt w to MAa 2 If A is in First 00 add A gt w to MAb for each terminal b in Follow A 3 If A is in First to and is in Follow A add A gt w to MA E quotH Ilidll E IHHH F quotII Ilidll F IIIIlvlcll llll 39 T quotII Ilidll T IIIIHIIIIII 1 E 39 9 T E First E quot A Follow E39 quotquotquotquot 2 E 9 T E TI quot71quot TI IHHIIIIII 3 I A 4 T gt F T39 terminals 5 TI F T 3 E 6 A n E t T 7 F gt c E e r T 8 id m F S Predictive Parsing Table id E T E T E E T E T FT FT T F T A F id E where S is the grammar39s push start symbol n A A for each ruIeA gtoo wasequence of I pop pushoo terminals and variaples m t a foreach terminal a GA a pop push start symbol of grammar onto stack repeat let X top of stock c next input if terminalCX then if Xc then pop X read c else errorm fi else nonterminalCX if MXc Y1 Y2 Yk then pop X push Yk YK l Y1 Y on top else errorm fi fi until stack is empty and input 39gt Portlanst et 394 Example Parse lTop of stack Stack E x T E x F T E x id T E x T E E T E T E F T E id T E T E El K1 K1 K1 K1 K1 K1 K1 K1 K1 K1 mmmmmmmmmmmmm Portlangin tate ERSITY CS3 I Computational Structures Nondeterminism Theorems about Finite State Automata Lecture 4 ea Portlansmgm Review Formal Definition of DFA A deterministic finite automaton is a 5tuple Q A 6 qo F where 1 Q is a finite set called the states 2 A is a finite set called the alphabet 3 6 Q x A gt Q is the transition function 4 qo is the start state and 5 F g Q is the set of final states e Portlansll gr Let s build some DFAS Design DFAs that recognize each of theselanguages abb x y x yabb x yxyy ea Portlansim Nondeterminism In the FSA that we have seen so far there is exactly one action to be taken on each input symbol that s what it means for 6 to be a function In a nondeterministic FSA several Choices may exist at each step e Portlanm Example of NFA O 1 O 1 A A 1 How does it differ from a DFA 1 some states have multiple transitions on a given input 2 some states have no transition on an input 3 some transitions have label A e Portlanst ets Formal Definition A nondeterministic finite automaton is a 5tuple Q A 6 qo F where 1 Q is a finite set called the states 2 A is a finite set called the alphabet 3 6 Q x A U A gt Q is the transition func on 4 qo is the start state and 5 F g Q is the set of final states e Portlansll tgf Nondeterministic Computation What does it mean for an NFA to take a step when there are multiple possibilities at each step What about A the NFA makes all possible transitions in parallel or equivalently the NFA clones itself and one clone explores each possibility an NFA can reach a dead end gets stuck an NFA accepts its input if any of the clones reaches a final state can Portlansll gr Recap Two kinds of FSA Deterministic for each input there is exactly one next state Nondeterministic for each input there may be zero one or many next states NFA can also make Atransitions at any time Both are formally defined by a 5tuple the details of the transition function differ e Portlan sgm FSA can be used to define languages Lfsa w e A w is accepted by fsa Unsubstantiated rumor For any RE there is an NFA that accepts the language defined by that RE The class of regular languages and the class of languages recognized by NFA are the same can Portlansmer Unsubstantiated Rumor NFA anol DFA are of equivalent power that is for any NFA there is an equivalent DFA Le a DFA that recognizes the same language and vice versa but that s obvious why is it obvious e Portlansmer First Rumor RE gt NFA Theorem is by construction start with an RE show how to build an NFA from it show that the NFA accepts the same language as the RE How can we possibly do this when there are an infinite number of REs can Portlansim NFA construction datatype 39a NFA NFA of allStates State list alphabet 39a list transitions State 39a Label State list startState State FinalStates State list Fun allStates NFA allStates alphabet transitions startState FinalStates allStates Fun startState NFA allStates alphabet transitions startState FinalStates startState Fun alphabet NFA allStates alphabet transitions startState FinalStates alphabet Fun transitions NFA allStates alphabet transitions startState FinalStates transitions Fun FinalStates NFA allStates alphabet transitions startState FinalStates finalStates Portlangin tate ERSITY fun NFAfor C x let val q0 newState C val ql newState C in NFA allStates q0 ql alphabet x transitions q0 Label startState q0 finalStates ql Hein construction I I7 Portlan iN Etkasllt 393 NFAFor Lambda let val a0 newState C val ql newState C in NFA aIIStates q0 ql alphabet E transitions Ca EmptyLabel q1 startState q0 FinalStates ql es Portlansmgm NFAFor Empty 139 Portlanst tgm let V01 q newState C V01 Q1 newState C in NFA aIIStates q0 Q1 alphabet transitions startState q0 FinalStates q1 NFAfor ConcatCrel re2 let val m NFAforCrel val n NFAforCreZ in NFA allStates allStates m allStates n alphabet union alphabet m alphabet n transitions transitions m transitions n map fn each gt each EmptyLabel startState n finalStates m startState startState m finalStates finalStates n 3 ea Portlangl gilt2 NFAfor Unionre1 re2 let val m NFAforre1 V 3 val n NFAforreZ E5 val start newState magi val final newState NFA allStates start final allStates m allStates n startState start finalStates final alphabet union alphabet m alphabet n transitions start EmptyLabel startState m start EmptyLabel startState n transitions m transitions n map fn source gt source EmptyLabel final finalStates m map fn source gt source EmptyLabel final finalStates n end Portlan iN nite 397 NFAfor Star rel let val m NFAforre1 val start newState val final newState NFA allStates start final allStates m startState start alphabet alphabet m finalStates final transitions start EmptyLabel final start EmptyLabel startState m map fn each gt each EmptyLabel final finalStates m map fn each gt each EmptyLabel startState m finalStates m transitions m end ea Portlangl gm Are we done yet Sir How do we know that this construction tells us what to do for all REs Does the resulting FSM accept the same language as is described by the RE e Portlanmm What about the ML program The program doesn t prove the theorem But it does let us test that the construction works for a large number of examples and that in each case strings in the language of the RE are accepted by the FSM e Portlanm Converting an NFA to a DFA When an NDFA computes at any time it is in a set of states or equivalently there are a set of machines each of which is in one state the set grows and shrinks as the computation continues Key idea build a DFA whose states represent sets of states in the NFA e Portlansll gr A Closure a useful buildingblock in the construction of a DFA for all NFA states s the A Closure of s written Ms is defined by 1seMs 2 if p 6 Ms and 6p A q then q 6 Ms e Portlansim Hein Example 1116 Ji q L cg Portlansmgm CS3 I Computational Structures Properties of Contexfree Languages Lecture 2 c9 Portlang gae What do we know about CF Languages Any CF language can be recognized by a PDA The language recognized by a PDA is CF Some CF languages are deterministic but others are not Some languages are LLk but others are not for any k The union of two CF languages is CF The product of two CF languages is CF The catenation closure of a CF language is CF Not all languages are CF epor anlglem 2 Stereotypical nonCF language anbncn n 2 O gt VVhy gt Notice the importance of loops in the argument epor anm 3 The Pumping Lemma for Contextfree Languages If a CF language is finite o If a CF language is infinite gt any grammar must contain a recursive production gt eg S ruRy R WRX w where either v or x must be nonempty gt then we can derive 0 8 gt uRy gt uwy o 8 gt uRy gt uvay gt uvwxy o 8 gt uRy gt uvay gt uvvaxy gt uvvwxxy o 8 gt uRy gt uvay gt uvvaxy gt uvvvaxxy gt uvvvwxxxy e Portlanme More generally 8 gt uvwxy S u v w x y Why must there be at least two subtrees derived from some R Portlansmrs More generally lt gt Portlansmers Theorem Statement If L is a contextfree language then there is a number p called the pumping length such that for all strings z e L lzl 2 p zcan be divided into 5 pieces 2 uvwxy satisfying 1 for each i 2 O uviwxl39y e L 2 lvxl gt O 3 lvwx sp e Portlan lat Using the Pumping Lemma 0 prove that L anbncn n 2 O is not CF Assume that L is CF and derive a contradiction gt pick z anPcP where p is the pumping length gt z gtp so we can write zzuvwxy where l vxl gt 0 lvwxl Sp and uviwxiy iS in L gt v can t contain all three letters Nor can x 0 because lvwxl s p gt if v contains two letters say a and b then any string containing v2 can t be in L Same for x gt so v and x must have the form aior bior of or gt so uviwxiy can t have the same number of as bs and cs epor anlgggm 8 Exercises 0 Prove that C aiiy39ck O s i sj s k is not CF 49 Portlanme Let the pumping length be p and consider the string z wmmmc Then the pumping lemma says that we can divide z uvwxy where val gt 0 vaxl Sp and uviwxiy iS in L Both 1 and x can t be empty If either 1 or x contains a and b or a and c then 122 or x2 will contain the as and bs or bs and cs in the wrong order Hence either 1 or x contains just as just bs or just cs Now there are three cases to consider Now there are three cases to consider 1 The as don t appear Now consider uvowxoy and compare with uvwxy The string uvowxoy still has p as but fewer bs or cs Hence uvowxoy 6E C 2 The bs don t appear So either as or cs must appear in vorx because both vaI gt 0 If as appear then uvzwxzy contains more as than bs If cs appear then uvowxoy contains fewer cs than bs Either way the pumped string 92 C 3 The cs don t appear In this case uvzwxzy contains more as or bs than cs and so the string uvzwxzy e C Thus z can t be pumped and we have a contradiction can P0rt1an9i tet9 390 provethatDww we01isnotCF c9 Portlang gae 0 prove that D 0quot02quot03quot n 2 0 is not CF 4 Portlanel mhe 392 0 prove that A 0711710711quot n 2 0 is not CF 49 Portlang gae 08311 Computational Structures Turing machines and other models of computation Lecture I5 epor antgggm 39 Recognizable vs Decidable A language L is Turing recognizable if some Turing machine recognizes it gt Some strings not in L may cause the TM to loop gt Turing recognizable recursively enumerable A language L is Turing decidable if some Turing machine decides it gt To decide is to return a definitive answer the TM must halt on all inputs gt Turing decidable decidable recursive ca Portlanme Decidable Language A1 OZnin Z Decidable by M1 1 Sweep right counting Os and crossing off every other 0 2 if in 1 there was a single 0 accept 3 otherwise if in 1 there was an odd number of Os halt 4 return the head to the left and repeat from 1 epor anm 3 in State Reading Wme Move New State I 0 k R 0 State diagram 0 o o R 7 1 k L 4 1 0 0 R 2 for M1 1 X X R 1 2 k R 9 2 0 gtlt R 1 7 x x p 7 4 k R 0 4 0 0 L 4 4 gtlt gtlt L 4 State 0 I m looking at first input 7 4 4 L h symbol 7 o gtlt R 1 7 gtlt gtlt R 7 State 7 I ve seen exactly one 0 0 on this pass State 1 I ve seen an even number of 0s on this pass State 2 I ve seen an odd number of 0s on this pass State 4 I m skipping back to the start Portland State Variations on TMs Machines that can only go L or R but not 8 Machines with a explicit Reject state Multihead Turing machines Multitape Turing machines Nondeterministic Turing machines None of these variations change the power of the machine can Portlanme Determinism doesn t matter How to prove this gt Simulate a nondeterministic Turning machine by a deterministic Turing machine gt DTM has to run each of the NTM computations in turn until it finds one that accepts or it has tried them all What s the problem gt One of the NTMs may run for ever What s the solution epor anm 7 Elaborating some Definitions Configuration gt Tape Contents nonblank gt State gt Head position Representation uqv gt Tape Contentsuv gt Stateq gt Head position reading first leftmost symbol ofv epor anm 8 Recall In manual execution of TM last lecture we wrote a sequence of configurations When can one configuration follow another Call this the yields relation can Portlanme Special configurations Start configuration of M on x gt A configuration with start state of M to the left on x Accepting Configuration of M gt A configuration containing the halt state of M Rejecting Configuration of M gt A configuration not containing the halt state that has no successor configurations by the yields relation for M Halting Configuration eitherAccepting or Rejecting e Portlanme 390 Basic definitions Deterministic TM gt The moves are all functionally determined by the state and symbol at the tape head 0 Nondeterministic TM gt The moves are a general relation with potentially multiple applicable moves 0 In both cases the set of all moves is finite e Portlanme quot Deterministic AcceptReject The deterministic machine M accepts x if gt There is a series of configurations 0 that begins with a start configuration for M on x o is related by the yields relation for M 0 ends with an accepting configuration for M The deterministic machine M rejects x if gt There is a series of configurations 0 ends with a rejecting configuration for M e Portlanme 392 Nondeterministic Accept and Reject The nondeterministic machine accepts if there is some sequence of configurations that leads to an accepting configuration The nondeterministic machine rejects if all possible sequences of configurations lead to a rejecting configuration can Portlanme 393 Trees of Computations The nondeterministic computation can be viewed as a tree or possible computations gt Nodes are configurations gt The daughters of a configuration are all configurations reachable in one step by yields This is a finitely branching tree gt What does the tree look like for our composite number program gt Can we order the alternatives can Portlanme 394 Simulation Strategy To simulate the NTM construct a DTM that will search this tree of possible NTM computations What kind of search strategy should we use How can we express that strategy can Portlanme 395 Tree addresses An ordered tree with fanout bounded by k can be addressed by strings over the alphabet O k1 What ordering on strings reflects a breadth first search strategy can Portlanme 396 Construction Use a 3 tape DTM to simulate the NTM gt Tape 1 contains the input and is never changed gt Tape 2 contains the tree address gt Tape 3 is the simulation tape Initialize the tree address to empty string gt At each stage 0 Copy the input tape to the simulation tape 0 Simulate the NTM branch described by address tape 0 Accept if NTM accepts 0 Otherwise increment tree address next string in lexicographic order can Portlanme I7 Correctness If NTM accepts x will DTM accept x o If DTM accepts x will NTM accept x e Portlansm t Rejection As constructed we never reject When can we reject e Portlanm Universal Turing Machines A universal Turing Machine 1 takes as input a description of some other Turning machine M and 2 an input string w and 3 simulates the action of M running on w 4 halting looping or accepting as does M e Portlanme 2 How to build a Universal TM Remember a Universal TM U must still have only a fixed and finite set of states a finite alphabet and therefore a finite set of instructions 8 Relabel the TM that we are simulating S to use states from Nat and symbols from ai i 6 Nat gt That s OK there are bound to be enough gt Pick a fixed alphabet for U say I u 01 gt Encode the instructions of S in Th e Portlanme 2 Let U have three tapes tape 1 stores the encoding of S tape 2 stores the input string tape 3 records the state of S encoded in FL U does the following Writes the start state on tape 3 o If the state on tape 3 is a final state then halt otherwise read the current symbol from tape 2 and find the instruction on tape 1 that applies 0 Write the new state onto tape 3 and perform the indicated write and move operations on tape 2 e Portlanme 22 Why are UTMs important They capture the idea of a storedprogram computer gt First storedprogram computer Manchester Baby was built in 1948 gt Earlier computers Harvard Mk I and ENIAC were fixed program computers The idea of a computer that can take another computer as input is key to proofs of undecidability and unsolvability can Portlanme 23 What is Computation What does computable mean gt A computer can calculate it gt There is some formally described execution process and a formally described set of instructions an algorithm that describes how to get the answer epor anlglare 24 Examples Generating strings from a grammars gt derivation is the process the algorithm is encoded in the rules of the grammar Accepting a string in a state machine gt Executing an ML program gt These are all Models of Computation e Portlanme 25 The Power of Model We know that some models of computation are more powerful than others gt CFG are more powerful than Regular Grammars gt DFAs have the same power as NFAs gt Turing machines are more powerful than PDAs Is there a most powerful model can Portlanme 26 Turing s Thesis Our intuitive notion of computation is precisely captured by the formal device known as a Turing Machine There is no model of computation more powerful than a Turing machine Why is this a thesis and not a theorem e Portlanme 27 Steampowered Turing machine Sieg Hall I987 What about Alonzo Church o The Turing thesis is usually called the ChurchTuring r Thesis in honor of Alonzo Church 1903 1995 gt Working with his students J Barkley Rosser Steven C Kleene and Alan M Turing Church established the equivalence of the Lambda calculus recursive function theory and Turing machines gt They all capture the notion of computability Portland ats Other Notions of Computability Simple a programming language with while loops Recursive Functions Lambda calculus MarkovAlgorithms Post Algorithms Post Canonical Systems Portlanmete 3 Simple Hein p 776 A Simple program is defined as follows 1 V an infinite set of variables that take values in Nato and are initially O 2 S statements which are either 21 While statements while V O do 8 0d 22 Assignments V 0 V1 succV2 V1 predV2 or 23 a sequence of statements separated by 3 S is a simple program can Portlanme 339 Note that pred0 O to ensure that we stay in Nato Can we compute anything interesting with this language 0 yes 32 can Portlan9i tet9 Macro Statement Simple Code for Macro XY X suCCY X predX X3 X 0 X suCCX X suCCX X suCCX XXY I Y while 175 0 do X suCCX I pred od Loop Forever X 0 X suCCX while X73 0 do Y2 0 od repeat S until X 0 S while X73 0 do Sod Figure 132 Some simple macros Let s try x y xlty while xlty do 8 od 49 Portlansl tgte 33 Markov Algorithms A Markov Algorithm over an alphabet A is a finite ordered sequence of productions x gty where x y e A Some productions may be Halt productions gt eg abc gt b ba gt x halt Execution proceeds as follows 49 Portlanme 34 1 Let the input string be w 2 The productions are scanned in sequence looking for a production x gt y where x is a substring of w 3 the leftmost x in w is replaced by y 4 If the production is a halt production we halt 5 If no matching production is found the process halts 6 If a replacement was made we repeat from step 2 e Portlanme 35 Note that a production A gt a inserts a at the start of the string What does this Markov algorithm do aba gtb ba gtb b gta e Portlanm 36 Example Proof using the Pumping Lemma for Regular Languages Andrew P Black 22 April 2008 Prove that the language E w E 01 w has an equal number of Os and ls is not regular Proof We prove the required result by contradiction So7 we assume that E is regular Then7 by the pumping lemma7 there is a pumping length p such that all strings s in E of length p or more can be written as s myz where 1 3473A 2 izyigmnd 3 zyiz E E7 for all i 2 0 Consider the string 3 01 11 Clearly7 p E E and lsl 2 197 so we should be able to nd a decomposition of s into myz that meets conditions 173 above How about z z A7 y 01 11 This meets conditions 1 and 3 But no7 it fails to meet condition 2 If l my l g 197 then my must contain just 0s and no 1s Hence7 y must contain just 0s and no 1s So7 if s myz E E7 it follows that 2 E7 since m2 has fewer 0s than myz but the same number of 1s Thus7 we have found a string in E that cannot be pumped7 which contradicts the assumption that E is regular D Note that we get to choose a string 3 to suit our purposes If7 instead7 we had chosen 017 then we would not have been able to complete the proof Why not Because that particular string can be pumped But this is not a problem the lemma says that all strings can be pumped7 so all that we need do is nd one string that cannot be pumped7 and we have the contradiction that we are looking for What is the minimum pumping length for the language L 0001 The minimum pumping length for a language L is the smallest p such that all strings of length p or more can be pumped In L 0001 1 000 can t be pumped because 0000 is not in L 2 0001 can be pumped put z 0007 y 17 z A So the minimum pumping length is 4 How many states would you expect to nd in a DFA recognizing L CS3 l Computational Structures Regular Languages and Regular Expressions ca Portlanmae Recap We have defined two different things 0 Regular Languages 0 the sets Q A a and the sets we can make by applying U and to other regular languages mathematical object sets of sequences from the alphabet Regular Expressions formulae involving E A a parenthesis and the operations juxtaposition and 0 just syntax with no meaning yet can Portlan9l tefs 2 The meaning of an RE 0 We ll write M as the meaning function Mtaa MEAA M W M Pct Mtp M q M EPCIJ M p U M q M p M p e Portlanmae Analogy the meaning of Numerals First define numerals In words The digits are 0 1 2 3 4 5 6 7 8 9 A decimal numeral is either a digit or a decimal numeral followed by a digit 0 Or as a grammar D gto123456789 N leND e Portlansl eis 4 The meaning of a Numeral JMEOJO JME1J1 JM22 JME3J3 JME4J4 JMESJ5 JME6J6 JME7J7 JME8J8 JME9J9 e Portlanmrs ZMENDJ1OXJWENJJMEDJ Example M257 10xM25M7 jMMZS 1OXJM2M5 10gtlt25 20525 7M257 10gtlt257 2507257 0 abC abc Example RES abcd 0 abC 0abY lt13 Portlanmrs Properties of RES Hein 1112 1 properties RTTR R0QRE R R R RTRGT properties RE 2 GR 6 RA AR 2 R RST RST 3 Distributive properties RS T 2 RS RT 8 TR SR TR N e Portlanmrs lt13 Portlanmrs More properties Closure properties 4 A A 5 R RR R R R RARARARRARR R R R RAR Rk 1RkR 6 RR RR 7 R S R S RS RSR RSR 8 RSR RSR 9 RS A R SS RS 2 A R R S for any 19 2 1 for any k 2 1 We can prove all of these properties of REs by examining the meaning of the REs as sets of strings Example M RT m R U m T defn of M T U m R U is commutative M TR defn of Let s try some others a Portlanmae 9 Bonng This is all pretty mechanical An ideal task for a computer program 0 How can we represent REs in a programming language can Portlanmae 390 Regular Expressions in ML The Regular Expressions 1 A Q and a are regular expressions for all a E A datatype RE Lambda 2 HR and S are regular eXpress1ons then the followmg eXpress1ons are l Empty also regular R R S R 39S and R C of string Union of RE RE I Concat of RE RE Not only does this de ne a datatype it also de nes 6 Star of RE 39 funct1ons that make values of the type inFixr 5 This will be the inFiX union operation it will have precedence 5 inFixr 6 AA and this will be the inFiX concatenation operation with higher precedence 6 Fun Lambda M b b C prope rty 2 2 0 Properties of Regular Expressions a AA Lambda a property 22 Empty AA b Empty property 21 a AA Empty Empty property 2 1 a AA b Concat a b Fun Empty II b b property 12 a II Empty a property 12 a II b Union a b Portland State UNIVERSITY Portland State String mapipulation Funcitons Fun Firststr string Stringextractstr 0 SOME 1 The First character oF a string Fun reststr string Stringextractstr 1 NONE the rest oF the string all chars but the First The Function string makes an RE From a string So string quotiFquot ConcatC quotiquot C quotFquot This is For convenience and readability Fun string str case Stringsize str 0F 0 gt Lambda 1 gt C str gt Concat C First str string rest str matches anything so this is the deFault case val alpha C quotaquot II C quotbquot C quotcquot The same as UnionC quotaquot UnionC quotbquot C quotcquot but more readable val digit C quot0quot C quot1quot C quot2quot val ite string iFquot string quotthenquot string quotelsequot val ident alpha AA Star alpha digit val number digit AA Star digit UNIVERSITY generate r generates a list containing some oF the strings in the language represented by the RE r In general any RE containing Star will generate an inFinite language to avoid waiting Forever this implementation oF generate limits itselF to 012 and 3 repetitions on the starred item Fun generate Union lr generatel generater generate Concat lr product generate l generate r generate Star r generate Lambda generate r product generate r generate r product generate r product generate r generate r generate C c c generate Lambda quotquot generate Empty product ll 12 is the quotlanguage productquot oF the two lists ll and 12 See Hein page 43 and product ys product XXs ys map Fn y gt XAy ys product xs ys val p C p val q C quotqquot val r C quotW val z C quot0quot val i C quot1quot Portland State UNIVERSITY CS3 I Computational Structures Topdown parsing with a Parse Table Lecture II a Portlana tgm Recall the theory whereSis the grammar39s push S start symbol A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or Por anst gi 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or 2 replace A on the stack with a where A gtoo is a rule of the grammar derive eporaansiaem 2 Recall the theory whereSis the grammar39s push S start symbol A A for each rule A gtoo co a sequence of pop pushoo terminals and variables gi a for each terminal a GA P0P At each step PDA can either 1 read input a iff a is on the stack match or 2 replace A on the stack with a where A gtoo is a rule of the grammar derive How to choose which A gtoo Portlangin Etkasilt 2 Recall the Practice and moreConcat C if couldBeSimple lookahead then let val x closureC val y moreConcatC in case y of NONE gt SOME X moreConcat a closure moreConcat A SOME 2 gt SOMECConcathz end else NONE and couldBeSimple LeFtParen true couldBeSimple Hash true couldBeSimple Zero true couldBeSimple Single true couldBeSimple False Portlangin tate ERSITY Topdown predictive parsers Use an explicit stack instead of recursion Represent the transitions of the PDA in a table rather than as code Choice of action of the parser which production to use to expend the stack symbol represented by three functions Nullable First Follow 0 Nullable Can a symbol derive the empty string False for every terminal symbol Nullable term or nonterm gt bool 0 First all the terminals that a nonterminal could possibly derive as its first symbol First term or nonterm gt set term First sequenoeterm nonterm gt set term 0 Follow all the terminals that could immediately follow the string derived from a nonterminal Follow nonterm gt set term can Portlan sgm Example First and Follow Sets E gt T E E gt T E I First E quotquot quotidquot Follow E quotquotquotquot E A A First F quotquot quotidquot Follow F quotquotquotquot quotquot T gt F T FirstT quotquot quotidquot FollowT quotquotquotquotquotquot First E quotquot A Follow E39 quotquotquotquot A T F T First T39 quotquot A Follow T39 quotquotquotquotquotquot T gt A F 39 E a First of a terminal is itself F gt i d 0 First can be extended to be defined on a sequence of symbols Nullable if is in Firstsymbol then that symbol is nullabe Sometimes rather than let be a symbol we use an additional function Nullable gt Nullable E39 true gt NullableT39 true gt Nullable for all other symbols is false E gtTE39 E39 gt TE39 E39 gt T gtFT39 T39 gtFT39 T39 gt F gt E F gtid 7 Computing FIRST 0 Use the following rules until no more terminals can be added to any FIRST set 1 if X is a terminal FIRSTX X 2 if X gt A is a production then add A to FIRSTX or set nullable of X to true 3 if X is a nonterminal and X gt Y1 Y2 Yk add a to FIRSTX if a in FIRSTY and for all jlt i nullable Yj equivalently A in FlRSTY eg if Y1 can derive A then if a is in FIRSTY2 a is surely in FIRSTX as well Example First Computation 0 Terminals 5 g First First First 3 FAT 0 Empty Productions E A add A to FirstE39 add A to FirstT39 E i if 0 Other NonTerminaIs Computing from the lowest layer F up FirstF id FirstT39 A FirstT FirstF id FirstE39 A FirstE FirstT id 3333 Computing FOLLOW 0 Use the following rules until nothing can be added to any follow set 1 Place the end of input marker in FOLLOWS where S is the start symbol This is Hein s rule 1 2 If A gt a B b then put everything in FlRSTb except A into FOLLOWB This is Hein s rule 3 3 If there is a production A gt a B orA gt a B b where FlRSTb contains A Le nullable b then put everything in FOLLOWA into FOLLOWB This is a combination ofHein s rules 2 amp 4 Example Follow Computation 0 Rule 1 Start symbol Add to FollowE 0 Rule 2 Productions with embedded nonterminals Add First to FollowE Add First to FollowE Add FirstE39 A to FollowT E gt T E39 Add FirstT39 A to FollowF E39 gt T E39 0 Rule 3 Nonterminal in rightmost position E 9T Add followE39 to followE39 doesn t do much T39 F T39 Add follow T to followT39 T39 gt A Add followT to followF since T39 gtA E gt 1 E gt I Add followT39 to followF since T39 gt A Table from First and Follow For each production A gt to do steps 1 3 below 1 For each terminal a in First to add A gt w to MAa 2 If A is in First 00 add A gt w to MAb for each terminal b in Follow A 3 If A is in First to and is in Follow A add A gt w to MA E quotH Ilidll E IHHH F quotII Ilidll F IIIIlvlcll llll 39 T quotII Ilidll T IIIIHIIIIII 1 E 39 9 T E First E quot A Follow E39 quotquotquotquot 2 E 9 T E TI quot71quot TI IHHIIIIII 3 I A 4 T gt F T39 terminals 5 TI F T 3 E 6 A n E t T 7 F gt c E e r T 8 id m F S Predictive Parsing Table id E T E T E E T E T FT FT T F T A F id E where S is the grammar39s push start symbol n A A for each ruIeA gtoo wasequence of I pop pushoo terminals and variaples m t a foreach terminal a GA a pop push start symbol of grammar onto stack repeat let X top of stock c next input if terminalCX then if Xc then pop X read c else errorm fi else nonterminalCX if MXc Y1 Y2 Yk then pop X push Yk YK l Y1 Y on top else errorm fi fi until stack is empty and input 39gt Portlanst et 394 Example Parse lTop of stack Stack E x T E x F T E x id T E x T E E T E T E F T E id T E T E El K1 K1 K1 K1 K1 K1 K1 K1 K1 K1 mmmmmmmmmmmmm Portlangin tate ERSITY Portlangin tate ERSITY If you can keep your head when all about you are losing theirs a Portlansmgm If you can keep your head when all about you are losing theirs its just possible you haven39t grasped the situation a Portlansim If you can keep your head when all about you are losing theirs its just possible you haven39t grasped the situation Rose Fitzgerald Kennedy a Portlansim What is the situation 5 days ago you were given an assignment to write an 11line program tests It s in a language that you ve never used before based on a concept algebras that you have forgotten about You saw some example programs in class but you didn t take notes eporaanm 2 CS3 I Computational Structures Finite State Automata es Portlansmgm Deterministic Finite State Automata A very simple form of computer Used in real life for control circuits Hardware control door circuits Software control telephone and network communications eportlanl gm 4 Example Door Controller As found at supermarket or airport The state diagram is a universally understood way of describing such a machine can Portlan9i at Plan view from rear pad pad door State Diagram REAR FRONT BOTH REAR NEITHER BOTH FRONT NEITHER Door Controller continued This FSA can also be represented as a transition function or transition table input signal NEITHER FRONT REAR BOTH state CLOSED CLOSED OPEN CLOSED CLOSED OPEN CLOSED OPEN OPEN OPEN This contains the same information as the diagram NEITHER emmm 6 FSA that recognize languages FSA accepts a string it o 1 it ends up in a final 1 state after reading that string from an input 0 tape 0 Start state indicated with 39 Final states indicated with C What language is accepted by the FSA in the figure as Portlanst at Let s try some examples 0 o 1 1 1 a 01 0 39 1O 39 001 110 3 Portlansmsm Formal Definition of DFA A deterministic finite automaton is a 5tuple Q A 5 qo F where 1 Q is a finite set called the states 2 A is a finite set called the alphabet 3 6 Q x A gt Q is the transition function 4 qo is the start state and 5 F g Q is the set of final states can Portlansll tgr Why use a formal definition 1 It is precise eg it says that 1 There can be no accept states F Q 2 6 is total so there is exactly one next state for each input symbols in the Alphabet 2 We can easily turn it into a computer program eporaanm 39 Example Diagram 1 Formal definition 1Q 2A 3QO 45 5F 9 Portlansmsm Example continued What strings are 1 I db h39 E cl l te Vt 393 9 o The set of all strings accepted by a FSM forms the language recognized by the FSM LW601 9 Portlansl et FSMS for Regular Languages What FSM recognizes the language Q What FSM recognizes the language A eporaanmm 393 What FSM recognizes the language a 4 can Portlansmgm What FSM recognizes the language a What FSM recognizes the language a over the alphabet a b eporaanmm 394 Another Example What language is recognized by this machine Portlanudu malts IS Formal Definition of FSM Computation Let M Q A 6 qO F be a FSM and let w wlewn be a string where each w E A M accepts w if there is a sequence of states ror1r2rn E Q such that 1 r0q0 2 609 w rl fori 1 2 3 rnEF can Portlanslt gr Language Recognition A machine M recognizes a language L if Lw M accept5w 7 e Portlansmgm ML definition of a FSM datatype 39a Label Label of 39a datatype State State of string datatype 39a FSM FSM of allStates State list alphabet 39a list transitions State 39a Label State list startState State FinalStates State list This defines the type FSM as a structure with Five named Fields eporaanmm 398 C Fun Fun Fun Fun Fun For convenience let39s deFine Five projection Functions that extract the Fields startState FinalStates allStates startState FinalStates startState startState FinalStates alphabet startState FinalStates transitions startState FinalStates FinalStates allStates FSM allStates alphabet transitions startState FSM allStates alphabet transitions alphabet FSM allStates alphabet transitions transitions FSM allStates alphabet transitions FinalStates FSM allStates alphabet transitions We are going to use lists to represent sets so we need to implement the set operation union the set membership test and an operation that adds a single element to the set We also deFine a Function setOF that turns an arbitrary list into a quotset listquot by removing duplication Fun union ll quota list E quota list ll union CE 12 12 union ees 12 union es add e 12 and member e l List exists Fn x gt x e l and add e l iF member e 1 then 1 else e 1 Fun setOF Portlandquot tate setOF e e setOF ees add e setOF es ERSITY Amazing Theorem The class of regular languages and the class of languages accepted by some FSM are identical eporaanmm 2 Nondeterminism In the FSA that we have seen so far there is exactly one action to be taken on each input symbol that s what it means for 6 to be a function In a nondeterministic FSA several Choices may exist at each step eporaanm 239 Example of NFA O 1 O 1 A A 1 How does it differ from a DFA 1 some states have multiple transitions on a given input 2 some states have no transition on an input 3 some transitions have label A eporaanmm 22 Formal Definition A nondeterministic finite automaton is a 5tuple Q A 6 qo F where 1 Q is a finite set called the states 2 A is a finite set called the alphabet 3 6 Q x A U A gt Q is the transition func on 4 qo is the start state and 5 F g Q is the set of final states eporaanlatgm 2 3 Nondeterministic Computation What does it mean for an NFA to take a step when there are multiple possibilities at each step What about A the NFA makes all possible transitions in parallel or equivalently the NFA clones itself and one clone explores each possibility an NFA can reach a dead end an NFA accepts its input if any of the clones reaches a final state eporaanmm 24 Contextfree Languages Lecture 8 eporaanm 39 Example derivation in a Grammar 0 Grammar start symbol isA A gt 0A1 A gt B B gt A r Derivation I1 Language 0 o o 1 1 1 3 Portlansmsm 2 A Fragment of English SENTENCE gt NOUN PHRAS39EVERB PHRASE NOUNPHRASE a CMPLXNOUN 1 CMPLXNOUNPREP PHRASE VERBPHRASE a CMPLXVERB CMPLX VERBPREP PHRASE PREPPHRASE PREPCMPLXNOUN CMPLXNOUN gt ARTICLE NOUN CMPLXVERB gt VERB 1 VERBNOUN PHRASE ARTICLE gt a the NOUN gt boy girl I flower VERB gt touches likes sees PREP a with What strings can be derived from this grammar cgt Portlan ssae 3 SENTENCE gt N0 UNPHRASEVERB PHRASE N0UNPHRASE gt CMPLXNOUN 1 CMPLXNOUNPREP PHRASE VERBPHRASEgt 2 CMPLX VERB j CMPLX VERBPREP PHRASE A d O n PREP PHRASE 2 PREPXCMPLX NOUN CMPLX NOUN gt ARTICLE NOUN CMPLX VERB gt VERB i VERBHNOUN PHRASE ARTICLE a i the ltNOUNgt gt boy i girl flower VERB gt touches I likes sees PREP gt with ltSENTENCEgt 2 ltNOUNPHRASEgt ltVERBPHRASEgt 2 ltCMPLXNOUNgt ltVERBPHRASEgt 2 ltARTCLEgtltNOUNgt ltVERBPHRASEgt 2 the ltNOUNgt ltVERBPHRASEgt 2 the girl ltVERBPHRASEgt 2 the girl ltCMPLXVERBgt 2 the girl ltVERBgt 2 the girl sees ceraporaanmg 4 Another 13 mummy gtthe gtthe gtthe gtthe gtthe gtthe gtthe gtthe SENTENCE gt N0 UNPHRASEVERB PHRASE N0UNPHRASE gt CMPLxNOUN 1 CMPLXNOUNPREP PHRASE VERBPHRASEgt H CMPIX VERB j CMPLX VERBPREP PHRASE PREP PHRASE PREPXCMPLX NOUN CMPLXNOUN gt ARTICLE NOUN CMPLX VERB gt VERB i VERBHNOUN PHRASE ARTICLE a i the ltNOUNgt boy i girl flower VERB gt touches I likes sees PREP gt with ltSENTENCEgt gt ltNOUNPHRASEgt ltVERBPHRASEgt 3 ltCMPLXNOUNgt ltVERBPHRASEgt 3 ltARTCLEgtltNOUNgt ltVERBPHRASEgt ltNOUNgt ltVERBPHRASEgt girl ltVERBPHRASEgt girl ltCMPLXVERBgtltPREPPHRASEgt girl ltVERBgt ltPREPPHRASEgt girl sees girl sees girl sees girl sees ltPREPPHRASEgt ltPREPgtltCMPLXNOUNgt with ltCMPLXNOUNgt with a flower Formal definition of CFG A Contextfree grammar is a 4tuple V Z R S where 1 V is a finite set call the variables non terminals 2 Z is a finite set called the terminals 3 R is a finite set of rules where each rule is a variable and a string 3 e V u Z 4 S e V is the start symbol eporaanlatgm 6 Derivation Let u v and w be strings in v u Z and let A gtw be a rule in R then uAv gt uwv read uAv yields uwv We say that u gt v read u derives v if u v or there is a sequence U1 U2 Uk k20 st u gtU1gtU2gt gtukgtv The language of the grammar is w e 2 8 ii w e Portlansmer Leftmost Derivation In general in any step of a derivation there are several variables that can be reduced by rules of the grammar In a leftmost derivation we Choose to always reduce the leftmost variable can Portland gm ltSENTENCEgt gt ltNOUNPHRASEgt ltVERBPHRASEgt es Portlansmgm gt ltCMPLXNOUNgt ltVERBPHRASEgt gt ltARTICLEgtltNOUNgt ltVERBPHRASEgt gt the ltNOUNgt ltVERBPHRASEgt gt the girl ltVERBPHRASEgt gt the girl ltCMPLXVERBgt gt the girl ltVERBgt gt the girl sees Example Grammar arithmetic expressions Consider grammar G4 V Z R EXPR V is EXPR TERM FACTOR and Z is a x C The rules are EXPR gt EXPRTERM TERM TERM gt TERMXFACTOR FACTOR FACTOR gt EXPR la Deriveaaxa Por anmie 39 EXPR EXPR TERM lt gt TERM TERM FACTOR FACTOR a FACTOR Portlang g t e39 I I lt a a x EXPR EXPR TERM lt lt7 m gt FACTOR FACTOR FACTOR t a lt a X Notice how the grammar gives the meaning a axa Pm1antt mts quot Another grammar ltEXPRgt ltEXPRgtltEXPRgt ltEXPRgtXltEXPRgt ltEXPRgt Ia Derive aaxa 2 es Portlansmgm This grammar is ambiguous there are two different leftmost derivations that derive a a x a ltEXPR EXPR EXPR EXPR EXPR EXPR mm EXPR EXPR EXPR i a a X a a a X a P r wst tst 393 Parsing Parsing is the process of going from a sentence string in the language to a derivation tree Topdown parsing starts at the top with the startsymbol of the grammar can Portlansmem PDAS for Topdown parsing whereSis the grammar39s push S start symbol A A for each rule A gtoo 00 a sequence of pop pushoo terminals and variables Qi a for each terminal a EA pop eporaanm 395 Bottomup parsing pUSh A w for each rule A gtoo w a sequence of pOp pushA terminals and nonterminals 8LL push a for each terminal a GA where S is the grammar39s start symbol c139 Portlanst tet 396 Building a CFG from a PDA Hein s Algorithm 128 This is the algorithm that I started going through in class The variables of the grammar are S the start symbol and Xij for each stack symbol X and each pair of states i and j in the PDA This gets complicated fast Most of these variables will never appear on the rhs of a production and so can be removed I couldn t get it to work on a simple example and certainly couldn t prove it correct eporaanmm 397 Building a CFG G from a PDA P Sipser s Lemma 227 L t t E r F 1 We seek to build a grammar that has the property in the box 2 If an input string drives P from state i with empty stack to state j with empty stack it will aslo move it form i to j with arbitrary stuff on the stack eporaanm 398 Building a CFG G from a PDA P o to g With p with empty Start by simplifying the problem Modify P so that it has a start state 0 a single final state go so that it starts and finishes with an empty stack and so that each transition pushes or pops a single symbol onto the stack fir tab How to do this Now we need to write a grammar with start symbol Aago such that it satisfies the invariant eporaanm 399 How can P move from state p when it s stack is empty First move must be to push some symbol onto the stack Last move must be to pop a symbol off the stack Maybe the stack does not become empty in between or maybe it does So there are two cases eporaansim 2 Suppose that the stack does not become empty in between First machine reads a pushes some X and goes to some state say r Then it does something maybe complicated ending in some state s Finally it pops the same X reads b and goes to state C This corresponds to the grammar production qu gt aArsb where Ars satisfies the invariant ltgtPortlan9i sgrs 239 In pictures T Stack helght generated by AM Input string gt w generated by Ara 6 Portlan 3e 22 Suppose that the stack becomes empty again in between T Stgtck helght w generated Y AM In ut strin p g p 7 q WWId generated generated by Am by AM then the rule qu gtAprArq does the job 43gt P rt1anst 5 tlt2 23 Construction Let P Q 2P60clgt Construct G with variables qu p q e Q start symbol A50 terminals 2 and rules R defined as follows 1 For eachp E Q the rule App gt A e R 2 For each p q r E Q the rule Am gt AprArq e R 3 For each p q r s E Q X e Rand 6119 6 2A 6paA 3 r X and 6sb X 3 q A the rule qu gt aAer e R eporaanm 24 Proof The proof that this construction works requires two things 1 Any string generated by Am will in fact bring P from state p with empty stack to state q with empty stack Sipser Claim 230 and 2 All strings capable of bringing P from state 9 with empty stack to state q with empty stack can in fact be generated by Am Sipser claim 231 eporaansim 25 Example PDA for aquot bquot a b A push A BC IOOIO A push hop 9 Portlansmgm 26 Example PDA for aquot bquot e Portlansmgm Does not meet the restrictions 26 Example PDA for aquot bquot 1 Stack must start and finish empty e Portlansmgm Does not meet the restrictions 26 Example PDA for an bn 1 Stack must start and finish empty 2 Single final state e Portlansim Does not meet the restrictions 26 Example PDA for aquot bquot 1 Stack must start and finish empty 2 Single final state 3 Every transition must be a push or a pop a Portlanm Does not meet the restrictions 26

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

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

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

#### STUDYSOUP REFUND POLICY

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

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

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

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