CPSC 313 Lecture Notes - Regular Language, January 30, Joule

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

Document Summary

We can use something called a p umping lemma to help us prove that certain languages are nonregular. When considering dfas, we see that they have a bounded amount of memory. We also note that dfas cannot accept languages where it is necessary to count arbitrary numbers. Claim : the language l = {anbn|n 0} over = {a, b} is not regular. Intuition : any dfa would have to count the number of a"s and match it with the number of b"s. P roof : suppose there is a dfa m = (q, , , q0, f ) that accepts l. consider the states (q0, ai) for i = 0, 1, 2, Since there is an unbounded number of i"s, but q is nite, 0 m < n : (q0, an) = Since m accepts ambm, we have ( nish later. Intuition : suppose w l is long enough. We can break w into three pieces.