Obtain a DFA to accept strings of a’s and b’s starting with the string ab.

Solution: It is clear that the string should start with ab and so, the minimum string that can be accepted by the machine is ab.

To accept the string ab, we need three states and the machine can be written as

where q₂ is the final or accepting state. In state q₀, if the input symbol is b, the machine should reject b (note that the string should start with a). So, in state q₀, on input b, we enter into the rejecting state q₃. The machine for this can be of the form

The machine will be in state q₁, if the first input symbol is a. If this a is followed by another a, the string aa should be rejected by the machine. So, in state q₁, if the input symbol is a, we reject it and enter into q₃ which is the rejecting state. The machine for this can be of the form

Whenever the string is not starting with ab, the machine will be in state q₃ which is the rejecting state. So, in state q₃, if the input string consists of a’s and b’s of any length, the entire string can be rejected and can stay in state q₃ only.

The resulting machine can be of the form

The machine will be in state q₂, if the input string starts with ab. After the string ab, the string containing any combination of a’s and bs, can be accepted and so remain in state q₂ only. The complete machine to accept the strings of a’s and b’s starting with the string ab is shown in figure.

The state q₃ is called trap state or rejecting state.

In the set notation, the language accepted by DFA can be represented as

L = {ab(a + b)ⁿ |n ≥ 0}

Or

L = {ab(a + b)^*}

Therefore the DFA which accepts strings of a’s and b’s starting with the string ab is given by M = (Q, S, d, q₀, F), where

Q = {q₀, q₁, q₂, q₃}, ∑ = {a, b}, q₀: initial state, F = {q₂}, and the transition function d is defined as

To accept the string abab: The string is accepted by the machine.

(q₀, abab) = d ( (q₀, aba), b)

= d (d ( (q₀, ab), a), b)

= d (d (d (d (q₀, a), b), a), b)

= d (d (d (q_1, b), a), b)

= d (d (q₂, a), b)

= d (q₂, b)

= q₂ ∈ F.

To reject the string aabb:

 (q₀, aabb) = d ( (q₀, aab), b)

= d (d ( (q₀, aa), b), b)

= d (d (d (d (q₀, a), a, b), b)

= d (d (d (q_1, a), b), b)

= d (d (q₃, b), b)

= d (q₃, b)

= q₃ ∉ F.

Therefore the string aabb is not accepted by the machine.