What is the easiest way to determine the accepted language of a deterministic finite automaton (DFA)?

Question

I'm new to automata theory and I'm currently working on some exercises on determining the accepted language of DFAs. I was wondering whether there exists some clever strategy to determine the accepted language of a DFA. For example, I have the following DFA over the alphabet {0, 1}:

What is be the best approach to solve such problems?

Answer 1

We can start analyzing from the final state $q_2$: $$ u(0|1)^* $$ where $u$ is a prefix word. Arrival only via accepting a $1$ coming from $q_1$ or $q_0$: $$ v1(0|1)^* $$ where $v$ is another prefix word. Joining the start state $q_0$ via the upper (via $q_1$) or lower edge (direct): $$ (00)^*(0|\epsilon)1(0|1)^* $$ which simplifies to $$ 0^*1(0|1)^* $$

Answer 2

This is a very small DFA, so I’d use a fairly ad hoc approach. Notice first that its language is precisely the set of words that reach $q_2$: once it gets to $q_2$, it stays there, and there is no other acceptor state. Thus, we need only see what words get to $q_2$.

Clearly we need a $1$ at some point. It can come right away, thanks to the $q_0\overset{1}\longrightarrow q_2$ transition, or it can come after some $0$s. How many $0$s? One $0$ gets us to $q_1$, at which point a $1$ takes us to $q_2$. Two $0$s take us back to $q_0$, at which point a $1$ takes us to $q_2$. In fact, it appears that any number of $0$s (including none at all) followed by a $1$ will get us to $q_2$. Thus, anything conforming to the regular expression $0^*1$ gets us to $q_2$. After that we can have anything at all, so the language of the DFA must be $0^*1(0+1)^*$.

Answer 3

Any path from the start state to an accept state is a string in your language, and if you find a loop from a state A back to itself then you can repeat the loop string as many times as you want after you reach A and then if you can reach an accept state from A then this will lead to an infinite family of accepted strings where the loop string is repeated some arbitrary number of times. Applying this kind of reasoning, you can often figure out the regular expression for a not-too-complicated DFA. If you want an algorithm that is guaranteed to work for any minimal DFA, see

http://regex-automaton.com/conversion_of_dfa_to_regular_expressions.php

Answer 4

This question will help you. You have to solve the system of equations under the monoid $(\Sigma, \circ, \epsilon)$ :

$$\begin{cases} \Xi_0 = 0 \Xi_1 \cup 1 \Xi_2 \\ \Xi_1 = 0 \Xi_0 \cup 1 \Xi_2 \\ \Xi_2 = (0 \cup 1) \Xi_2 \cup \left\{\epsilon \right\} \end{cases}$$

for $\Xi_0$.