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?
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$.