CPSC 121 Lecture Notes - Lecture 41: Dfa Records, Halting Problem, Sequential Logic
CPSC 121 verified notes
41/41View all
Document Summary
Cpsc 121 lecture #41 regex to dfas (pt. Topics included: dfas and nfas, limitations of computing. Recap: to turn a regex expression into a dfa : we turn the regex expression into a nfa, we then turn the nfa into a dfa. [s2, s3, s5: at maximum, the nfa can have 2n-1 subsets for sn nodes. (source: belleville, lecture 41, slide 48, the top 2 figures above are nfas, while the bottom two figures are partial. Dfas: the partial dfas utilize a subset of states, dfa generators generate their nfa"s subset of states. 200 a"s , it will end in the same state as it would have if it only went through 100 a"s. Now if we give it 100 b"s, it would think it went through the same amount of states because 200 and 100 is the same to it.
