in Theory of Computation edited by
3,785 views
20 votes
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?

  1. The automaton accepts $u$ and $v$ but not $w$
  2. The automaton accepts each of $u, v,$ and $w$
  3. The automaton rejects each of $u, v,$ and $w$
  4. The automaton accepts $u$ but rejects $v$ and $w$
in Theory of Computation edited by
3.8k views

1 comment

Can someone explain DFA to regular expression using state elimination method
0
0

3 Answers

31 votes
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$
edited by

4 Comments

Is (ab*a)*b(a+b(ab*a)*b)* correct?
3
3
right.
1
1
@megha : (ab*a+ba*b)*ba* this should be the correct RE.
1
1
0 votes
0 votes

(D) is the answer.

0 votes
0 votes

Only accepts u,it reject v bcoz its not ended in final state and language is not accepting srting w.

correct answer-D

correct me if im wrong. 

Answer:

Related questions