Find a finite automata that recognizes $L=\{w\in\{0,1,2\}^*\mid\text{$w$ has one $1$ and odd number of $0$}\}$

Question

Find a finite automata that recognizes $$L=\{w\in\{0,1,2\}^*\mid\text{$w$ has only one $1$ and odd number of $0$'s}\}.$$

---

I don't think it is possible to construct such automata, but I am not able to prove it.

I have considered this question: Find automata for $S\to01X\mid0S,\;X\to2X\mid1Y,\;Y\to2Y2\mid0$ but I am not able to split the language into $L_i$ sublanguages.

Is $L$ regular or not?

Answer 1

Generally, languages that are not regular require remembering an arbitrarily large amount of information. This language is not an example of this, as all you need to know is the current parity of the number of $0$s, and whether you have seen at least 1 and at most 1 $1$.

So, here's a DFA that reads the language:

$$Q=\{0,1,2\}\times\{0,1\}$$

$$\delta((a,b),c)=\begin{cases}(a,b)&c=2\\(\min(a+1,2),b)&c=1\\(a,1-b)&c=0\end{cases}$$ $$q_0=(0,0)$$$$F=\{(1,1)\}$$

The corresponding regex is $$2^*(0(2^*02^*0)^*2^*1(00)^*+2^*(02^*02^*)^*12^*0(2^*02^*0)^*2^*)$$

Answer 2

A 4-state automaton suffices:

$\hskip 100pt$