Finite State Automaton

Question

I have a question from my Computer Science Maths exam from May. I have a repeat exam on Tuesday. I'd really appreciate it if someone could help :)

Question Determine whether the automaton M recognizes the words

• λ
• aba³b²a
• ab²a³

My Answer

• ???
• No. It does not recognise this word
• Yes. It recognises this word

Am I correct for part 2 and 3? What's the answer to part 1?

Answer 1

In order for an automaton to recognize $\lambda$, the empty word, its initial state must be an acceptor state. Here $s_0$ is the initial state, and the only acceptor state is $s_3$, so $M$ does not recognize $\lambda$.

You are correct that $M$ does not recognize $aba^3b^2a$: it goes from state $s_0$ in turn to $s_0$, $s_1$, $s_2$, $s_3$, $s_3$, $s_0$, $s_1$, and $s_2$, which is not an acceptor state.

You are also correct that $M$ does recognize $ab^2a^3$; the state path here is $s_0,s_0,s_1,s_1,s_2,s_3,s_3$.