What is the language recognized by the finite automaton?

Question

I have no idea how to approach this?

Answer 1

We are dealing with a deterministic finite automaton according to the provided picture. It is defined as a $5$-tuple $(Q, \Sigma, \delta, q_0, F)$.

• The set of states: $Q=\{\{1,2\}, \{1,2,3\}, \{2,3\}\}$
• The set of input symbols $\Sigma=\{a,b, \epsilon\}$
• The transition function $\delta: Q \times \Sigma \to Q:(\{1,2\},a) \mapsto \{1,2,3\}$, $(\{1,2,3\},a) \mapsto \{1,2,3\}$, $(\{1,2,3\},b) \mapsto \{2,3\}$, $(\{2,3\},b) \mapsto \{2,3\}$, $(\{2,3\},a) \mapsto \{1,2\}$
• The inital state $q_0:=\{1,2\}$
• The set of accept states $F \subseteq Q$, which is $Q$

So you always start with $a$ or $\epsilon$ (notice that the empty word is accepted because the initial state is an accept state).

Example of accepted words: $aabbb$, $a$, $aba$

Example of unaccepted words: $b$, $bbabaaaaaba$

Can you go from here?

Answer 2

It would be helpful to think of an automaton as some kind of "Snakes and Ladders Game". The circles which represent states correspond to the squares in the board game. The arrows represent movement from one square to another. The label on the arrow specifies which input ("dice throw") leads to that move. In board game there is a designated square reaching which is the goal. Here some states are marked specially to designate final state(s).

The language recognized by an automaton is the sequence of dice throws (inputs) which start from a specially marked initial state and lead to the final state.

The problem you stated was "I have no idea ...". Now I have given you an Idea that will help you solve this kind of problems.