CPSC 313 Lecture Notes - Jyj, Glossary Of Ancient Roman Religion

• School: University of Calgary
• Department: Computer Science
• Course: CPSC 313
• Professor: Philipp Woelfel

Document Summary

Let l be regular and m = (q, , , q0, f ) be a dfa for l. Let the states in q be q0, , qn 1. Choose m := n + 1 = |q| + 1. Consider an arbitrary w l, such that |w| m. Let the sequence of states that the dfa visits while processing w be. Among the rst m + 1 > |q| states visited, there is some state that is repeated. There is a state q = qir = qiz , z m, so that m visits states. q0, qi1 , qi2, , qik q0, qi1, qi2 , , qir , , qiz , , qik. Let x be the pre x of w that is processed until q is reached for the rst time, and xy the pre x until q is reached for the second time. Then |y| 1 and |xy| m, and. (q, yi) = q for any i 0.