Introduction: Parasitic numbers are nonnegative integer numbers $($possibly very long$),$ the

sequence of digits of which exhibits the following property $-$ if multiplied by the lowest digit,

called the base digit, the digits in the result form the same sequence except the last one that jumps

to the beginning. For example, in the decimal numeral system the cyclic number ending with $4$ is

Indeed, $1025644=410256.$ It is obvious that $0$ and $1$ are parasitic numbers by

themselves.

There is a simple algorithm that computes on digit$-$by$-$digit basis a parasitic number with

the given base digit:

Initialize the carry with $0$ ;

Multiply the last digit by itself and add the carry to the result;

Assign the units of the obtained result to the next digit;

Assign the tens of the obtained result to the carry;

Multiply the next digit by the last digit and add the carry;

Return to step $3$;

Stop the process when the last two digits are $10($the carry remains $0).$

The step$-$by$-$step implementation of the outlined algorithm for the shortest parasitic number

ending with $4$ in the decimal numeral is shown below:

$(2)(2)(1)$

Task $1$: Construct in the alphabet ${}_{10}=\{0,1,2,3,4,5,6,7,8,9\}$ a DFA $A=\{S_1,{}_{10},s_1,{}_1,F_1\}$

that checks if the input is a parasitic number. It accepts integer numbers in decimal notation written

in the reversed order. In other words, the base digit is written in the first input cell. For example,

the following input words are accepted: $"0","1","111","465201".$

Hint: consider an indexed set of states $s_{bcd}in{Q}_1,$ where each multiplication step in the

algorithm is represented by a state with three indexes $b,c$ and $d$ that correspond to the values of

the base digit, the current carry and the next digit respectively.

Task $2$: Construct in the alphabet ${}_{10}=\{0,1,2,3,4,5,6,7,8,9\}$ an NFA $B=\{S_2,{}_{10},S_2,{}_2,F_2\}$

that checks if the input is a parasitic number. It accepts integer numbers in decimal notation written

in the regular order. In other words, the base digit is written in the last input cell. For example, the

following input words are accepted: $"0","1","111","102564".$

Task $3.$ Write a regular expression that describes all parasitic numbers in $4-$base numeral system.

Task $4$: Repeat Task $2$ in $4-$base numeral system. Construct in the alphabet ${}_4=\{0,1,2,3\}$ an

NFA $C=\{S_3,{}_4,S_3,{}_3,F_3\}$ that checks if the input is a parasitic number. It accepts integer numbers

in $4-$base notation written in the regular order. Draw the diagram of the NFA $C.$

Task $5$: Convert the NFA $C$ from Task $4$ into DFA $D.$ Draw its diagram.