Can someone explain DFA to regular expression using state elimination method

Dark Mode

3,785 views

20 votes

In the automaton below, $s$ is the start state and $t$ is the only final state.

Consider the strings $u = abbaba, v = bab, \text{and} w = aabb$. Which of the following statements is true?

- The automaton accepts $u$ and $v$ but not $w$
- The automaton accepts each of $u, v,$ and $w$
- The automaton rejects each of $u, v,$ and $w$
- The automaton accepts $u$ but rejects $v$ and $w$

31 votes

Best answer

$${\begin{array}{l|l|l|l}

\textbf{for u}& \textbf{for v}& \textbf{for w} \\\hline \delta(s,abbaba) & \delta(s,bab) & \delta(s,aabb) \\\hline

\quad \vdash \delta(x,bbaba) &\quad \vdash \delta(t,ab) &\quad \vdash \delta(x,abb) \\\hline

\quad \vdash \delta(x,baba) &\quad \vdash \delta(t,b) &\quad \vdash \delta(s,bb) \\\hline

\quad \vdash \delta(x,aba) &\quad \vdash \mathbf{s} - \textbf{rejected} &\quad \vdash \delta(t,b) \\\hline

\quad \vdash \delta(s,ba) & &\quad \vdash \mathbf{s} - \textbf{rejected} \\\hline

\quad \vdash \delta(t,a) & & \\\hline

\quad \vdash \mathbf{t} - \textbf{accepted} & & \\\hline \end{array}}$$Correct Answer: $D$

\textbf{for u}& \textbf{for v}& \textbf{for w} \\\hline \delta(s,abbaba) & \delta(s,bab) & \delta(s,aabb) \\\hline

\quad \vdash \delta(x,bbaba) &\quad \vdash \delta(t,ab) &\quad \vdash \delta(x,abb) \\\hline

\quad \vdash \delta(x,baba) &\quad \vdash \delta(t,b) &\quad \vdash \delta(s,bb) \\\hline

\quad \vdash \delta(x,aba) &\quad \vdash \mathbf{s} - \textbf{rejected} &\quad \vdash \delta(t,b) \\\hline

\quad \vdash \delta(s,ba) & &\quad \vdash \mathbf{s} - \textbf{rejected} \\\hline

\quad \vdash \delta(t,a) & & \\\hline

\quad \vdash \mathbf{t} - \textbf{accepted} & & \\\hline \end{array}}$$Correct Answer: $D$