What method should you follow to show what a DFA does?

81 Views Asked by At

I'm specifically looking for help analyzing the following DFA. What steps would one follow to show what language this particular DFA accepts? To me it seems quite random, and I can't figure out a decisive way of showing that it accepts language $L$.

Note: $q_0$ is the start state and $q_3$ is the final state.

enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

The first part of your DFA is $b*a$, this puts you in state q1.

Then to get to an accept state, you can cycle between q2 and q1 until you either go straight to q3 or go through q2 to q3. That is $(ab)*(aa|b)$.

From an accepting state, you get to another accepting state by maintaining the same number of a and b $\pmod 3$. That means either: aaa, bbb, ab, ba, aabb, or bbaa.

So altogether: $(b*a)(ab)*(aa|b)(aaa|bbb|ab|ba|aabb|bbaa)*$

You can also factor the last term to get: $(b*a)(ab)*(aa|b)(a(b|a(a|bb))|b(a|b(b|aa)))*$

Alternatively, you could encode your DFA as a pair of matrices, one for inputs of 'a' and one for inputs of 'b':

$$M_a = \begin{array} {c|c|c|c|c|} & q0 & q1 & q2 & q3 \\ \hline q0 & 0 & 1 & 0 & 0 \\ \hline q1 & 0 & 0 & 1 & 0 \\ \hline q2 & 0 & 0 & 0 & 1 \\ \hline q3 & 0 & 1 & 0 & 0 \\ \hline \end{array}$$

$$M_b = \begin{array} {c|c|c|c|c|} & q0 & q1 & q2 & q3 \\ \hline q0 & 1 & 0 & 0 & 0 \\ \hline q1 & 0 & 0 & 0 & 1 \\ \hline q2 & 0 & 1 & 0 & 0 \\ \hline q3 & 0 & 0 & 1 & 0 \\ \hline \end{array}$$

Looking at $(M_a + M_b)^n\,_{q0, q3}$ will tell you how many strings of length $n$ are accepted. Your encoding depends on what you know about $L$.

0
On

The automaton accepts the set of all words $w$ in $\{a,b\}^*$ which satisfy both the following conditions:

(1) $w$ contains at least one $a$;

(2) the number of $a$s in $w$, minus the number of $b$s, is a multiple of $3$.

To see this informally, note that firstly there must be an $a$, otherwise $w$ is "stuck" in state $q_0$. Once there has been an $a$, the word gets to state $q_1$, then it moves one step "clockwise" for every $a$ it contains, and one step "anticlockwise" for every $b$.