Question

Let Σ = {0,1}. Prove that the language { w | w contains the substring 01001 } is regular by providing a finite automaton to recognize the language. Include a state diagram, formal description, and informal justification for the correctness of your automaton.

Answer 1

Regular expression for given language containing substring "01001" =

The deterministic finite automation/state diagram for the given language is shown in the below diagram:

In the above DFA a string can be accepted only if it contains substring "01001"

It is deterministic because for every state there is transition for both values 0 and 1.

Initial state is , final state is .

Set of all states

Set of inputs

Transition function

Since regular expression can be written for the given language and Determionistic Finite Automata (DFA) can be constructed for the given language so it is a regular language.