程序代写代做代考 prob7

prob7

Problem 7

(a)

Where

(b)

UFA doesn’t exist.

Suppose UFA exists, its number of states is . Now for a Finite Automaton A with states .
After UFA reads ‘s#’, it will begin simulating A. However, if for a string, Automaton A enters
more than states, than the UFA can’t simulate the state transition, because it only has
states.

Thus, we have contradiction, UFA doesn’t exist.

Problem 7
(a)
(b)