Write and test a method that simulates a general finite automaton. Your program should enable the computer to simulate any given finite automaton and then to simulate, for any given word, step$-$by$-$step, how this automaton decides whether this word is accepted by the automaton.

The input to this method should include the full description of the corresponding finite automaton:

the number N of states; these states are q$0,...,$ qN $1$; we assume that q$0$ is the start state; for simplicity, we describe the states by the corresponding integers $0,...,$ N;

the number M of symbols; these symbols are s$0,...$ sM $1$; for simplicity, we describe the symbols by the corresponding integers $0,...,$ M;

an integer array state$[$n$][$m$]$ whose elements describe to what state the finite automaton moves if it was in the state qn and sees the symbol sm; and

a boolean array final$[$n$]$ whose elements describe, for each state qn$,$ whether this state is final or not.

When simulating a finite automaton, your program needs to keep track, at each moment of time, of the current state. Initially, the state is q$0--$ which is described by number $0.$

Turn in:

a file containing the code of the method, and

a file containing the result of testing this method.

If you used any auxiliary program to test your method, also submit a file containing the code of this auxiliary program. Feel free to use Java, C$,$ C$++,$ Fortran, or any programming language in which the code is understandable.

No matter how hard you study $($S$),$ you need some rest $($R$).$ Ideally, you should study no more $8$ hours a day, with at least $16$ hours remaining, i$.$e$.,$ you should have twice as much time to rest as to study. Prove that the following language is not regular: the language L of all sequences of Ss and Rs in which there are at least twice as many Rs as Ss$.$ For example, the word SRSRRRR is in the language L$,$ while the word SRSRR is not in L$.$

Show, step by step, how the following pushdown automaton $--$ that checks whether a word consisting of letters S and R corresponds to a situation in which there are at least twice as many rest hours as study hours $--$ will accept the word RSR$.$ This pushdown automaton has three main states:

the starting state s$,$

the working state w$,$ and

the final state f$,$

and several intermediate states.

In the stack, in addition to the bottom symbol $$,$ we have:

either one or several Ns $--$ indicating the difference between twice the number of study hours and the number of rest hours so far $($if this difference is positive$),$

or one or several Rs $--$ indicating the difference between the number of rest hours and twice the number of study hours $($if this difference is positive$).$

The transitions are as follows:

From s to w$,$ the transition is $\backslash$epsi $,\backslash$epsi $->$ $$.$

From w to f$,$ the transition is: $\backslash$epsi $,\backslash$epsi $->\backslash$epsi $.$

From f to f$,$ we have two transitions: $\backslash$epsi $,$ R $->\backslash$epsi and $\backslash$epsi $,$ $ $->\backslash$epsi $.$

From w to w$,$ we have the following transitions:

If we see the symbol R and $ is on top of the stack, we keep the dollar sign and add R to the stack, i$.$e$.,$ we have transition R$,$ $ $->$ $ that brings us to an intermediate state a$1,$ and then the transition $\backslash$epsi $,\backslash$epsi $->$ R that brings us back to the working state.

If we see the symbol R and R is on top of the stack, we keep the top R and add another R to the stack, i$.$e$.,$ we have transition R$,$ R $->$ R that brings us to an intermediate state a$2,$ and then the transition $\backslash$epsi $,\backslash$epsi $->$ R that brings us back to the working state.

If we see the symbol R and N is on top of the stack, we delete the top N$,$ i$.$e$.,$ we have transition R$,$ N $->\backslash$epsi $.$

If we see the symbol S and $ is on top of the stack, we keep the dollar sign and add two Ns to the stack, i$.$e$.,$ we have transition S$,$ $ $->$ $ that brings us to an intermediate state a$3,$ then the transition $\backslash$epsi $,\backslash$epsi $->$ N that brings us to an intermediate state a$4,$ and then the transition $\backslash$epsi $,\backslash$epsi $->$ N that brings us back to the working state.

If we see the symbol S and N is on top of the stack, we keep the top N and add two more Ns to the stack, i$.$e$.,$ we have transition S$,$ N $->$ N that brings us to an intermediate state a$5,$ then the transition $\backslash$epsi $,\backslash$epsi $->$ N that brings us to an intermediate state a$6,$ and finally the transition $\backslash$epsi $,\backslash$epsi $->$ N that brings us back to the working state.

If we see the symbol S and R is on top of the stack, we first delete the top R from the stack, i$.$e$.,$ we have transition S$,$ R $->\backslash$epsi $,$ and move to an intermediate state a$7.$

If in this state, we see R on top of stack, we delete this R and go back to the working state; the transition is $\backslash$epsi $,$ R $->\backslash$epsi

if in this state, we see $ on top of the stack, we add N$,$ i$.$e$.,$ first we apply the transition $\backslash$epsi $,$ $ $->\backslash$epsi and go to the intermediate state a$8,$ and then we apply the transition $\backslash$epsi $,\backslash$epsi $->$ N$,$ and go to the working state.

Show, step by step, how the following grammar describing valid homework numbers will generate the expression $1$ab$.$ In this grammar, D stands for digit, L stands for