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

Don't confuse a non-final state with a dead state. Every dead state is non-final, but not every non-final

 state is a dead state. A non-final state is only dead if there is no possible path from it to any final state.

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

---

only string u is accept and v,w are rejected

Option D is correct

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

right.

---

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

---

Here only the string u is accepted as both v and w end up in non final states (just trace the path of the given string state by state you will see that they end up in non final states which means they're not accepted by the machine ie., not part of the language)

Answer 2

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 3

(D) is the answer.

Answer 4

Here only the string u is accepted as both v and w end up in non final states (just trace the path of the given string state by state you will see that they end up in non final states which means they're not accepted by the machine ie., not part of the language)

Answer 5

• Trace string $u = abbaba$:

  • $s \xrightarrow{a} q \xrightarrow{b} q \xrightarrow{b} q \xrightarrow{a} s \xrightarrow{b} t \xrightarrow{a} t$

  • Ends in state $t$ (Accepting state).

  • Result: $u$ is accepted.

• Trace string $v = bab$:

  • $s \xrightarrow{b} t \xrightarrow{a} t \xrightarrow{b} s$

  • Ends in state $s$ (Non-accepting state).

  • Result: $v$ is rejected.

• Trace string $w = aabb$:

  • $s \xrightarrow{a} q \xrightarrow{a} s \xrightarrow{b} t \xrightarrow{b} s$

  • Ends in state $s$ (Non-accepting state).

  • Result: $w$ is rejected.