GATE IT 2006 | Question: 3

Question

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?

• A. The automaton accepts $u$ and $v$ but not $w$
• B. The automaton accepts each of $u, v,$ and $w$
• C. The automaton rejects each of $u, v,$ and $w$
• D. The automaton accepts $u$ but rejects $v$ and $w$

Comments

Can someone explain DFA to regular expression using state elimination method

Answer 1

$${\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$

Comments

what language is generated ?

---

(ab*a+ba*b)*ba*

---

thank you sir

---

I think the language accepted is (ab*a+ba*b)*... how sir you are getting (ab*a+ba*b)ba*

---

 pallaviamu

your regular expression acccpt null .

---

Is (ab*a)*b(a+b(ab*a)*b)* correct?

---

right.

---

@megha : (ab*a+ba*b)*ba* this should be the correct RE.

Answer 2

(D) is the answer.

Answer 3

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.