CMPT 125 Lecture Notes - Lecture 23: Substring

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 125
• Professor: Igor Shinkar

Document Summary

Draw a dfa that accepts the language l1 = {abc, ac, bcc, bca} Draw a dfa that accepts the language l2 = {am(bc)n : m 0, n 0 } Draw a dfa that accepts the language l3 = all strings over {a,b} that contain the substring aab. Draw a dfa that accepts the language l4 = of all binary strings starting with 101. Draw a dfa that accepts the language l5 = of all binary strings ending with 1. Definition: a language l is said to be regular if there is a dfa that accepts l. Their concatenation l1l2 = {xy : x l1, y l2} is regular. The star closure (l1)* = {x1x2xt : for all i xi l1} is regular. The complement {0,1}* \ l1 = {x {0,1}* : x l1 } is regular. Proof: let"s prove it for the union of languages. Theorem: let l1, l2 be two regular languages.