menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

GATE2014-1-16

20 votes
5.5k views

Consider the finite automaton in the following figure:

 

What is the set of reachable states for the input string $0011$?

  1. $\{q_0,q_1,q_2\}$
  2. $\{q_0,q_1\}$
  3. $\{q_0,q_1,q_2,q_3\}$
  4. $\{q_3\}$
in Theory of Computation
edited by 5.5k views
0
What is meant by "reachable" over here? Set of terminating states for the string 0011 or set of all the states that can be visited by 0011?

For eg, if q2 was the only state where 0011 could terminate, then the answer will be {q2} or {q0,q1,q2}?

6 Answers

33 votes
 
Best answer

$q_0, q_1$ and $q_2$ are reachable from $q_0$ on input $0011$

Correct Answer: $A$


edited by
0
@Praveen Saini

Can't we move like this q0,q0,q0,q1 because q0 has both 0,1 inputs
1

@ Divya Bharti

It is NFA. So, if we consider for all possibility then answer is q0,q1,q2

1

@Praveen Saini Sir, can we also convert it to DFA and check, well, I did convert to DFA and found out that string 0011 end up in state {q0 q1 q2} I just want to confirm can we convert NFA to DFA and check it?

1
yes it will work fine.
0
@praveen

1.How to tackle this type of problem.

2.why not Q3 is considered as it is the final state as any string accepted by automata must end up at final state.

 

Please suggest

Thanks
0
Question is not about accept and reject of input
0
@Mr. Praveen, Can you please justify why we should not reach the final state?

Isn't it mandatory to reach final state for a given input string? I'm in doubt...
0
$\delta^*(q,w)=$contains only those states which have a walk from state q labelled w.
0
how to solve it fastly
11 votes

qo,q1,q2 can be reached in this nfa by enumerating all the possibilities


edited by
0 votes

q0,q1 and q2 are reachable from q0 on input 0011.

hence, reachable states={q0,q1,q2}. Option A is correct.

0 votes

{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
 

{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
 

{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
 

Hence δ (q0, 0011) = {q0, q1, q2}

0 votes

{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q0} . Hence δ (q0, 0011) = q0
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q0}, {q0 , 1 → q1} . Hence δ (q0, 0011) = q1
{q0 , 0 → q0} , { q0 , 0 → q0 }, {q0 , 1 → q1}, {q1 , 1 → q2} . Hence δ (q0, 0011) = q2
Hence δ (q0, 0011) = {q0, q1, q2}

0 votes

As you can see this was a very basic question so option A is the correct answer.

← Prev. Next →
← Prev. Qn. in Sub. Next Qn. in Sub. →
Answer:

Related questions

42 votes
4 answers
1
9.2k views
GATE2014-1-36
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
Which of the regular expressions given below represent the following DFA? $0^*1(1+00^*1)^* $ $0^*1^*1+11^*0^*1 $ $(0+1)^*1$ I and II only I and III only II and III only I, II and III
asked Sep 28, 2014 in Theory of Computation jothee 9.2k views
28 votes
2 answers
2
4.3k views
GATE2014-1-35
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.
asked Sep 26, 2014 in Theory of Computation jothee 4.3k views
14 votes
4 answers
3
2.4k views
GATE2014-1-46
The function $f(x) =x \sin x$ satisfies the following equation: $f''(x) + f(x) +t \cos x = 0$. The value of $t$ is______.
The function $f(x) =x \sin x$ satisfies the following equation: $f''(x) + f(x) +t \cos x = 0$. The value of $t$ is______.
asked Sep 28, 2014 in Calculus jothee 2.4k views
17 votes
3 answers
4
2.5k views
GATE2014-1-25
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server. The web browser requests a webpage using HTTP. The web browser establishes a TCP connection with the web server. The web server sends the requested webpage using HTTP. The web browser ... the domain name using DNS. 4, 2, 1, 3 1, 2, 3, 4 4, 1, 2, 3 2, 4, 1, 3
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server. The web browser requests a webpage using HTTP. The web browser establishes a TCP connection with the web server. The web server sends the requested webpage using HTTP. The web browser resolves the domain name using DNS. 4, 2, 1, 3 1, 2, 3, 4 4, 1, 2, 3 2, 4, 1, 3
asked Sep 26, 2014 in Web Technologies jothee 2.5k views
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...