Exercise $6$

Let $M=(Q,,,q_0,F)$ be a DFA. A state qinQ is reachable iff there is some string win${}^{**}$

such that hat$()(q_0,w)=q.$ Consider the following method for computing the set $Q_r$subeQ of

reachable states: define the sequence of sets $Q_r^i$subeQ where

$Q_r^0$:$=\{q_0\}$

$Q_r^{i+1}$:$=\{qinQ|EEpin{Q}_r^i,$EEain$,q=(p,a)\}$

Prove by induction on i that $Q_r^i$ is the set of all reachable states from $q_0$ using paths of

length $i.$

Give an example of a DFA such that $Q_r^{i+1}{Q}_r^i$ for all $i0.$

Change the inductive definition of $Q_r^i$ as follows:

$Q_r^{i+1}$:$=Q_r^i\{qinQ|EEpin{Q}_r^i,$EEain$,q=(p,a)\}$

Prove that there exists an $i_0$ such that $Q_r^{i_0+1}=Q_r^{i_0}=Q_r.$

Define the DFA $M_r$ as follows: $M_r=(Q_r,,{}_r,q_0,F{Q}_r),$ where ${}_r$:$Q_r{Q}_r$ is the

restriction of $$ to $Q_r.$

Explain why $M_r$ is indeed a DFA.

Prove that $L(M_r)=L(M).$ A DFA is called reachable or trim if $M=M_r.$