CPSC 313 Lecture Notes - Jyj, Regular Expression

97 views1 pages

Document Summary

L = {anbl | n (cid:54)= l} is not regular. Choose w such that |w| m, e. g. atbt(cid:48) Let xyz = w, such that |xy| m and |y| 1 y = ak 1 k m. We want to show: choose an i 0 such that xyiz / l. where t (cid:54)= t(cid:48) and t m. = at+(i 1)kbt(cid:48) at k+i kbt(cid:48) (t + (i 1)k = t(cid:48) k = i 1. Choose t(cid:48), t such that t(cid:48) t = m!, so t = m t = m + m! Let xyz = w such that |xy| m, |y| 1. / l. m k + i k = m + (i 1)k = m + m! 2 + 1. (cid:3) k k = m + m!. Consider the language l = {vwvr | v {a, b} , w {c, d} }. Consider {u | u contains no c"s or d"s} = l((a + b) ).

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents