--

--Question For Automata and Pattern Matching

--

1. 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) }.