The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged numberofstates
0
votes
2
answers
1
Minimal DFA
Given following NFA find the minimal equivalent DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

89
views
theoryofcomputation
minimalstateautomata
numberofstates
finiteautomata
+2
votes
1
answer
2
ME test series DFA states
The number of states in minimal DFA for strings starting with $ab^{2}$ and ending with $b$ over the alphabet $\left \{ a,b \right \}$ is__________. // doubt: minimal string should be $ abb $ right?
asked
Dec 13, 2018
in
Theory of Computation
by
Devwritt
Active
(
4k
points)

53
views
theoryofcomputation
numberofstates
minimalstateautomata
0
votes
1
answer
3
States in DFA
If NFA has 'n' states then how DFA can have 2^n states. Please help me in understanding how this is true. As per my understanding every DFA is NFA then how no of states can be more in DFA than nfa Please suggest Thanks
asked
Nov 10, 2018
in
Theory of Computation
by
Mayankprakash
Active
(
1k
points)

33
views
numberofstates
finiteautomata
theoryofcomputation
+1
vote
1
answer
4
Doubt DFA
1.The minimum no of state in DFA that accept L={an n is multiple of 3 but not 5} Ans 15 i did it and found that 3,5 relatively prime so 3*5=15 2.The minimum no of state in DFA that accept L={an n is multiple of 2 but not 4} Ans 4 and done and found that 2,4 not relatively prime so max(2,4) =4 Can't a Conclude it??? Edited. thanks for rectification.
asked
Nov 6, 2018
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
3.7k
points)

138
views
finiteautomata
minimalstateautomata
numberofstates
0
votes
0
answers
5
Dfa for no states
What is the difference between a dfa accepting epsilon moves and dfa accepting nothing? I have a dfa which has no states what will be the dfa this is regarding,this question https://gateoverflow.in/8362/gate2015152
asked
Oct 17, 2018
in
Theory of Computation
by
sripo
Active
(
1.3k
points)

36
views
minimalstateautomata
theoryofcomputation
finiteautomata
numberofstates
theoryofcomputation_
0
votes
0
answers
6
TOC : Minimum State in Finite Automata ( virtualgate )
For a binary string x = a0a1 · · · an−1 define val(x) to be the value of x interpreted as a binary number, where a0 is the most significant bit. More formally, val(x) is given by How many minimum states will be in a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either 4 or 5. Ans is 5 or 20?
asked
Oct 12, 2018
in
Theory of Computation
by
arya_stark
Active
(
1.5k
points)

43
views
theoryofcomputation
finiteautomata
minimalstateautomata
numberofstates
0
votes
1
answer
7
Number of States in TOC
Number of $2$ state DFA with designated initial state can be constructed over alphabet $\sum_{.}^{.}=\left \{ 0,1 \right \}$ and that accept empty language $\Phi$ is_______________
asked
Oct 6, 2018
in
Theory of Computation
by
srestha
Veteran
(
107k
points)

104
views
theoryofcomputation
minimalstateautomata
numberofstates
+1
vote
0
answers
8
DIGITAL LOGIC
A synchronous sequential circuit is to be designed to detect a bit sequence 0101 (overlapping sequence is included ). Every time this sequence is detected, the circuit produces an output ‘1’. What is the Minimum number of states that the circuit must have ? (a) 4 (b) 5 (c) 6 (d) 7
asked
Sep 21, 2018
in
Digital Logic
by
Gate Fever
Active
(
4.5k
points)

38
views
numberofstates
melay
digitalcircuits
0
votes
1
answer
9
Minimal DFA
Minimum states required for DFA that accepts : L = {w1 x w2  w,x belongs to {a,b}*  w1 >= 0, w2 > 1 and x >= 0 }.
asked
Sep 10, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.2k
points)

38
views
theoryofcomputation
minimalstateautomata
numberofstates
+1
vote
0
answers
10
Minimum number of States
Ans. 5
asked
Aug 30, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.2k
points)

72
views
minimalstateautomata
finiteautomata
theoryofcomputation
numberofstates
0
votes
1
answer
11
#Number of states in minimal DFA
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11. (a) 6 (b) 7 (c) 8 (d) 9
asked
Jul 31, 2018
in
Theory of Computation
by
himgta
Active
(
3.3k
points)

44
views
numberofstates
0
votes
1
answer
12
#Test series
What is the number of states in the minimal finite automata that accepts all the strings of a’s and b’s where each string starts with ‘bba’ and the length of the string is congruent to 2(mod 6). (a) 8 (b) 9 (c) 10 (d) 11
asked
Jul 30, 2018
in
Theory of Computation
by
himgta
Active
(
3.3k
points)

20
views
#
numberofstates
0
votes
1
answer
13
Minimum finite automata
Construct the Minimum FA that accepts all the string of 0's and 1's where A)Every String start and end with Zero. B)Every string Start and end with Same Symbol.
asked
Jul 10, 2018
in
Theory of Computation
by
suraj patel
(
71
points)

138
views
finiteautomata
theoryofcomputation
minimalstateautomata
numberofstates
0
votes
0
answers
14
Minimal dfa
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)
asked
Jun 12, 2018
in
Theory of Computation
by
Harshitha 123
(
99
points)

83
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
0
votes
3
answers
15
No of states in Minimal DFA
Ques: Let ∑= {0, 1} What will be the number of states in minimal DFA, if the Binary number string is congruent to (mod 8)? *[ Can anybody explain this as I am getting 8 states for this since remainders will be 8 (0,1,2,3,4,5,6,7). But the answer is 4].
asked
May 8, 2018
in
Theory of Computation
by
kislaya Pant
(
165
points)

231
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
+1
vote
1
answer
16
Minimal Final States in DFA
Ques: What are the number of final states in minimal DFA, where ∑= {a, b}, if every string starts with “aa” and length of the string is not congruent to 0 (mod 4).
asked
May 8, 2018
in
Theory of Computation
by
kislaya Pant
(
165
points)

110
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
+1
vote
1
answer
17
Number of States in FA
Can number of states in minimized DFA be less than number of states than minimal NFA from which it is converted?
asked
Apr 8, 2018
in
Theory of Computation
by
smsubham
Loyal
(
8.9k
points)

168
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
+1
vote
0
answers
18
Worst Case in NFA to DFA Conversion
Can you give an example of NFA which has n states and its corresponding DFA has 2^n states?
asked
Apr 8, 2018
in
Theory of Computation
by
smsubham
Loyal
(
8.9k
points)

136
views
theoryofcomputation
nfa
finiteautomata
numberofstates
+1
vote
2
answers
19
NFAE to DFA conversion. (which is the correct solution?)
1. Which solution is correct? (or both wrong!) 2. Does every 'DFA equivalent' of any NFA has same starting state? if not, please give any smallest example.
asked
Feb 27, 2018
in
Theory of Computation
by
ashishgateashish
(
93
points)

414
views
theoryofcomputation
nfa
finiteautomata
numberofstates
+3
votes
1
answer
20
Calculation of number of states in dfa without drwing dfa
Self doubt: Is there any method to calculate number of states in dfa e.g."x mod y" type of question without drawing dfa? Because in Gate time is vital factor.
asked
Jan 15, 2018
in
Theory of Computation
by
Sona Barman
Active
(
1.2k
points)

104
views
theoryofcomputation
finiteautomata
numberofstates
+2
votes
0
answers
21
minimal dfa
Consider the following grammar: $S\rightarrow aAbB$ $A\rightarrow aAbB$ $B\rightarrow bBϵ$ Then the number of states in a minimal D.F.A of the above grammar is ______________ ?
asked
Jan 15, 2018
in
Theory of Computation
by
junk_mayavi
Active
(
4.2k
points)

52
views
theoryofcomputation
minimalstateautomata
numberofstates
+2
votes
0
answers
22
Gate mock test
please explain answer given is 5
asked
Jan 4, 2018
in
Theory of Computation
by
VIKRAM KASANA
Junior
(
517
points)

170
views
theoryofcomputation
gate
mock
test
2018
finiteautomata
numberofstates
+2
votes
2
answers
23
#Strings DFA
$ L\ =\ \{\ a^mb^{2n}c^{3n}d^p\ \ m,n\ >=1\ ,\ p\ >\ m\} \\Find\ the\ number\ of\ strings\ of\ length\ <=\ 13$
asked
Dec 31, 2017
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
8.8k
points)

123
views
theoryofcomputation
finiteautomata
numberofstates
+1
vote
1
answer
24
MINIMAL DFA
asked
Dec 31, 2017
in
Theory of Computation
by
Aakanchha
Junior
(
761
points)

153
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
0
votes
1
answer
25
minimal Dfa
asked
Dec 3, 2017
in
Theory of Computation
by
Parshu gate
Active
(
5.1k
points)

73
views
numberofstates
minimalstateautomata
theoryofcomputation
0
votes
2
answers
26
TOC: DFA
Consider the following NFA: How many final states required in the equivalent DFA?
asked
Nov 20, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
26.5k
points)

164
views
theoryofcomputation
finiteautomata
numberofstates
+1
vote
1
answer
27
Minimum DFA Construction
Construct the minimum DFA accepting language L over {a, b} where the 5th symbol and the 10th symbol from LHS is different. It is given that the minimum DFA has 12 states. But I am getting many more states. Could someone please provide a diagram that involves only 12 states?
asked
Nov 17, 2017
in
Theory of Computation
by
humblefool
Active
(
1k
points)

156
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
+1
vote
0
answers
28
Number of states in DFA
L = {s ∈ (0 + 1)* d(s)mod5 = 2 or d(s)mod7 != 4} where d(s) is the decimal equivalent of the binary string s. How many states does the above DFA have? How many final states? Please explain your answer.
asked
Nov 12, 2017
in
Theory of Computation
by
Warlock lord
Active
(
3.5k
points)

141
views
theoryofcomputation
finiteautomata
numberofstates
+2
votes
1
answer
29
TOC : Number of states in DFA
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}
asked
Nov 9, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
26.5k
points)

178
views
theoryofcomputation
finiteautomata
minimalstateautomata
numberofstates
0
votes
2
answers
30
NUMBER OF STATES IN DFA
asked
Nov 6, 2017
in
Theory of Computation
by
Parshu gate
Active
(
5.1k
points)

158
views
finiteautomata
theoryofcomputation
numberofstates
Page:
1
2
next »
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
Recent Posts
PSU's
Decidability Slides
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
Follow @csegate
Gatecse
Recent questions tagged numberofstates
Recent Blog Comments
see this
pls share the link of RRBJE
It has not started yet!!
wbsedcl form fullup last date over ??
its really great thanks
47,139
questions
51,388
answers
178,064
comments
66,700
users