Paper 2, Section I, F

Automata and Formal Languages
Part II, 2021

Assuming the definition of a deterministic finite-state automaton (DFA) D=D= (Q,Σ,δ,q0,F)\left(Q, \Sigma, \delta, q_{0}, F\right), what is the extended transition function δ^\hat{\delta} for DD ? Also assuming the definition of a nondeterministic finite-state automaton (NFA) NN, what is δ^\hat{\delta} in this case?

Define the languages accepted by DD and NN, respectively, in terms of δ^\hat{\delta}.

Given an NFA NN as above, describe the subset construction and show that the resulting DFA Nˉ\bar{N} accepts the same language as NN. If NN has one accept state then how many does Nˉ\bar{N} have?