Question

Construct a DFA that accepts any strings over {a,b} that doesn't contain the string aabb in it.
​

Answer 1

Answer:

To solve this problem, first we will construct a DFA that accepts all strings over {a,b} that accepts the string aabb in it.

We can get the dfa that accepts all other strings except aabb by complementing above DFA. To do that, make all final states as non-final states and all non-final states as final states. The final DFA is shown below.

Answer 2

Explanation:

Construct a DFA that accepts any string over {0,1}that does not contain the string 011 in

it.

3. C