Question For Automata and Pattern Matching
a) Describe formally the language L consisting of all binary strings that do contain the string 001 as a substring. Write L as concatenation of three languages.
b) Prove that there are infinitely many strings in L and infinitely many strings not in L.
c) Construct a DFA M such that L(M ) = L. Prove the correctness of your construction.
d) Write a regular expression describing L. Prove the correctness of your construction.
I think the answer for question a should be
L1 = {u | u ? (0,1) }.
L2 = {001 }.
L3 = {v | v ? (0,1) }.
L = L1L2L3 = { u001v | u,v ? (0,1) }.