I have created 2 finite automata that accept 00, 01,10,11 and every even place number corresponds to the 2nd number while every odd place number corrensponds to the 1st.
The first finite automaton checks if the 2nd number is strictly smaller than the 1st (also the 2nd number is not 0).
example: [1]0[0]1[1]0 ->
101/010 it accepts it since it mean 5>2 and 2 != 0.
No matter how many 00,11 we have the criterion 1st > 2nd !=0 is not met, if we read 01 before 10 then it locks to Rejection(q1) since there is no way for the 2nd number to be smaller.
Is this an acceptable finite automaton; or there are improvements to be made?
The second finite automaton accepts strings where the 2nd number is 2 times bigger than the 1st (and 2nd != 0). The q5 state is the Rejection state so there are no edges out.
example: [1]0[0]1[1]0[0]1[1]1[0]1[1]0[0]1 -> 10101010/01011101 is rejected since 170/93 != 0.5 but [0]1[0]1[1]0[1]0[0]1[0]0[1]0[0] -> 00110010/1100100 (50/100) is accepted.
Are those 2 finite automata that solve my problems or they can be improved?
In both automatons q0 is the initial state.
Best Answer
The first automaton is fine; the second is not. For the second problem you need only four states. The key is that when you multiply a binary number $(b_1b_2\ldots b_n)_2$ by $2$, you bet $(b_1b_2\ldots b_n0)_2$: you simply shift the number to the left one place and append a $0$. Thus, the input of such a pair must look like this:
$$[0]b_1[b_1]b_2[b_2]b_3\ldots[b_{n-1}]b_n[b_n]0\,.$$
This is easier to read if we write the inputs as vertical pairs:
$$\begin{array}{rcc} \text{first number:}&0&b_1&b_2&\ldots&b_{n-1}&b_n\\ \text{second number:}&b_1&b_2&b_3&\ldots&b_n&0 \end{array}$$
Let $q^*$ be the initial state; the other states will be $q_0$, $q_1$, and $q_\infty$. The only acceptor state is $q_0$, and $q_\infty$ is the ‘dump’ (rejection state). The transition table is as follows:
$$\begin{array}{c|c|c} \text{current state}&\text{input}&\text{next state}\\\hline q^*&00&q^*\\ q^*&01&q_1\\ q^*&10,11&q_\infty\\\hline q_0&00&q_0\\ q_0&01&q_1\\ q_0&10,11&q_\infty\\\hline q_1&00,01&q_\infty\\ q_1&10&q_0\\ q_1&11&q_1\\\hline q_\infty&00,01,10,11&q_\infty \end{array}$$
The automaton remains in the initial state as long as it reads initial zeroes for both numbers. After that the automaton is in state $q_1$ when it has just read a pair $01$ or $11$, meaning that the first bit of the next pair must be $1$ for a valid input, and it is in state $q_0$ when it has just read a pair $00$ or $10$, meaning that the first bit of the next pair must be $0$ for a valid input.