FOR FREE MATERIALS

Some more DFA machine design example

Example1: 

Construct a DFA to accept a string containing a 0 followed by a 1.

RE1 = (0 + 1)*01(0 + 1)* 

Regular expression from DFA machine RE2 = 1*00*1(0 + 1)* and RE1 ≈ RE2.

Example 2: 

Construct a DFA accept a string containing two consecutive zero’s followed by two consecutive one’s.

Regular Expression RE = (0 + 1)*0011(0 + 1)* 

Example 3: 

Construct a DFA accept a string containing even number of zero’s and any number of one’s.

Regular expression RE1 = (1*01*01*)* + 1* 

Another Regular expression we write RE2 = (1 + 01*0)* and RE1 ≈ RE2.

Example 4: 

Construct a DFA to accept all string which do not contain three consecutive zero’s.

So, first we begin a DFA with three consecutive zero and then complement it to get the above answer.

Example 5: 

Construct a DFA to accept all string containing even number of zero’s and even number of one’s.

Example 6: 

Construct a DFA to accept all string which satisfy (X) mod 5 = 2.

Assignment:

Construct a DFA to accept all strings (0 + 1)* with an equal number of zero’s and one’s such that each prefix has at most one more zero than one’s and at most one more one than zero’s.