Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$

Question

Write a minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$

My attempt:

I currently haven't completed the solution, but my main problem is to find a simpler solution for this as the procedure I have followed so far doesn't seem to add up. What I did was:  

1) I created a DFA that you can see here 

2) Now I was following the procedure to minimize the DFA using the Systematic Reduction Method as shown here. (It isn't complete)

There has to be some way to make a DFA without going through all of this, but I simply can't think of it.

Answer 1

I assume that you are tring to draw minimal DFA for the language $L = \{(ab)^n \mid n \geq 0\}$.

Non - deterministic finite automata (NFA) will be:

Add all missing transitions, so it will became deterministic finite automata (DFA):

Note that it is minimal DFA because minimization algorithm for DFA will give $3$ states only:

$$ \begin{array}{c|cc} & a& b\\\hline q_0 & q_1 & \text{dead}\\ q_1 & \text{dead} & q_0\\ \text{dead} & \text{dead} & \text{dead}\\ \end{array} $$ Now, $\pi_0 = \{(q_0, \text{dead}), (q_1)\}$

$\pi_1 = \{(q_0), (\text{dead}), (q_1)\}$

$\pi_2 = \{(q_0), (q_1), (\text{dead})\}$

Therefore, $\pi_1 = \pi_2$. So, given DFA is minimal which has only $3$ states: $q_0, q_1,$ and, $\text{dead}$.

Answer 2

Let $L=\{(ab)^n :n\geqslant 0\}$. Clearly $\epsilon\in L$, so we must have the starting state $q_0$ be an accepting state. Since $a\notin L$ and $b\notin L$, we must have states $q_a$, $q_b$ which are not accepting states. As $ab\in L$ and $bb\notin L$, it is clear that $q_a$ and $q_b$ must be distinct states. We define transitions $\delta(q,x)$ for pairs of states $(q,x)$ by $$ \begin{array}{cc|c} q & x& \delta(q,x)\\\hline q_0 & a & q_a\\ q_0 & b & q_b\\ q_a & b & q_0\\ q_b & a & q_0\\ \end{array} $$ Since a string with two or more consecutive $a$'s is not in $L$, we see that a new state $q_{r,a}$ is needed for $\delta(q_a,a)$, and similarly a new state $q_{r,b}$ for $\delta(q_b,b)$. But any string which transitions into $q_{r,a}$ or $q_{r,b}$ is rejected, so there is no need to distinguish these states; let $q_r = q_{r,a} = q_{r,b}$. Define the rest of the transitions by $$ \begin{array}{cc|c} q & x& \delta(q,x)\\\hline q_a & a & q_r\\ q_b & b & q_r\\ q_r & a & q_r\\ q_r & b & q_r\\ \end{array} $$ then $M=(\{q_0,q_a,q_b,q_r\}, \{a,b\}, \delta, q_0, \{q_0\})$ is a DFA which recognizes $L$ with the minimum number of states.