FSM to be regular with atleast two 0's and at most two 1's

Question

Is it possible to construct a FSM to prove that the set $X$ is regular, where $$ X = \{s \in \{0,1\}^* \mid \text{$s$ contains at least two $0$'s and at most two $1$'s}\}\ ? $$

Answer 1

It is possible, you could show it using regular expressions and closure properties.

Let $L_1 = (\Sigma^*\mathtt{0}\Sigma^*\mathtt{0}\Sigma^*)$ and $L_2 = (\Sigma^*\mathtt{1}\Sigma^*\mathtt{1}\Sigma^*\mathtt{1}\Sigma^*)$, then

$$X = \big\{s \in \Sigma^* \mid \#_\mathtt{0}(s) \geq 2, \#_\mathtt{1}(s) \leq 2\big\} = L_1 \cap L_2^c$$

If you want to construct the automaton, it could look like the one on the left side (the labels aren't provided intentionally, fill them out yourself).

$\hspace{50pt}$

Observe the connection between the left side automaton and a form of product of the two automatons presented at the right side (a state in the product is accepting only if both components are accepting states). In fact the left is $X$, while the right-up is $L_1$ and right-down is $L_2^c$; it's not a coincidence that the product of automatons and intersection of languages are connected.

I hope this helps $\ddot\smile$

Answer 2

You need to store in the finite state how many 0s and how many 1s have been seen. So let the states be pairs of the form $\langle n_0, n_1\rangle$ where $n_0$ is the number of 0s and $n_1$ is the number of 1s seen so far, with $0\le n_0\le 2$ and $0\le n_1\le 3$. The start state is $\color{green}{\langle 0,0\rangle}$.

On reading a 0, the machine makes a transition from $\langle n_0, n_1\rangle$ to $\langle n_0, n_1+1\rangle$, except that if $n_1 = 3$ it stays in the same state. On reading a 1, the machine makes a transition from $\langle n_0, n_1\rangle$ to $\langle n_0+1, n_1\rangle$, except that if $n_0 = 2$ it stays in the same state.

The accepting states are exactly $\color{blue}{\langle 2,0\rangle}, \color{blue}{\langle 2,1\rangle}, $ and $\color{blue}{\langle 2,2\rangle}$ because these are the states where $n_0\ge 2$ and $n_1 \le 2$.