menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
IITH CSE interview M Tech RA Winter admission 2021
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.4k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent questions tagged number-of-states
Recent Blog Comments
This Year IISc is not taking students of computer...
Hi, could you please update us about the Mock...
Hi, just curious if there are any updates...
thanks himanshu2021. But I am asking for the page...
But IISc hasn't mentioned TCS as one of their...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Recent questions tagged number-of-states
0
votes
2
answers
1
Minimal DFA
Given following NFA find the minimal equivalent DFA
Given following NFA find the minimal equivalent DFA
asked
Dec 14, 2018
in
Theory of Computation
aditi19
416
views
theory-of-computation
minimal-state-automata
number-of-states
finite-automata
3
votes
2
answers
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?
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
Devwritt
230
views
theory-of-computation
number-of-states
minimal-state-automata
0
votes
2
answers
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
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
Mayankprakash
210
views
number-of-states
finite-automata
theory-of-computation
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.
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
Abhisek Tiwari 4
649
views
finite-automata
minimal-state-automata
number-of-states
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/gate2015-1-52
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/gate2015-1-52
asked
Oct 17, 2018
in
Theory of Computation
sripo
504
views
minimal-state-automata
theory-of-computation
finite-automata
number-of-states
theory-of-computation-
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?
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
arya_stark
115
views
theory-of-computation
finite-automata
minimal-state-automata
number-of-states
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_______________
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
srestha
327
views
theory-of-computation
minimal-state-automata
number-of-states
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
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
Gate Fever
366
views
number-of-states
finite-automata
digital-circuits
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 }.
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
Na462
200
views
theory-of-computation
minimal-state-automata
number-of-states
1
vote
0
answers
10
Minimum number of States
Ans. 5
Ans. 5
asked
Aug 30, 2018
in
Theory of Computation
Na462
207
views
minimal-state-automata
finite-automata
theory-of-computation
number-of-states
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
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
himgta
181
views
number-of-states
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
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
himgta
127
views
number-of-states
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.
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
suraj patel
862
views
finite-automata
theory-of-computation
minimal-state-automata
number-of-states
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)
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
Harshitha 123
152
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
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].
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
kislaya Pant
1.2k
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
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).
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
kislaya Pant
246
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
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?
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
smsubham
541
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
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?
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
smsubham
362
views
theory-of-computation
nfa-dfa
finite-automata
number-of-states
1
vote
2
answers
19
NFA-E 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.
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
ashishgateashish
993
views
theory-of-computation
nfa-dfa
finite-automata
number-of-states
3
votes
2
answers
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.
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
Sona Barman
759
views
theory-of-computation
finite-automata
number-of-states
2
votes
0
answers
21
minimal dfa
Consider the following grammar: $S\rightarrow aA|bB$ $A\rightarrow aA|bB$ $B\rightarrow bB|ϵ$ Then the number of states in a minimal D.F.A of the above grammar is ______________ ?
Consider the following grammar: $S\rightarrow aA|bB$ $A\rightarrow aA|bB$ $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
junk_mayavi
116
views
theory-of-computation
minimal-state-automata
number-of-states
2
votes
1
answer
22
Gate mock test
please explain answer given is 5
please explain answer given is 5
asked
Jan 4, 2018
in
Theory of Computation
VIKRAM KASANA
345
views
theory-of-computation
finite-automata
number-of-states
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$
$ 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
Tuhin Dutta
183
views
theory-of-computation
finite-automata
number-of-states
1
vote
1
answer
24
MINIMAL DFA
asked
Dec 31, 2017
in
Theory of Computation
Aakanchha
266
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
0
votes
1
answer
25
minimal Dfa
asked
Dec 3, 2017
in
Theory of Computation
Parshu gate
158
views
number-of-states
minimal-state-automata
theory-of-computation
0
votes
2
answers
26
TOC:- DFA
Consider the following NFA:- How many final states required in the equivalent DFA?
Consider the following NFA:- How many final states required in the equivalent DFA?
asked
Nov 20, 2017
in
Theory of Computation
rahul sharma 5
405
views
theory-of-computation
finite-automata
number-of-states
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?
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
humblefool
312
views
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
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.
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
Warlock lord
976
views
theory-of-computation
finite-automata
number-of-states
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}
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
rahul sharma 5
316
views
theory-of-computation
finite-automata
minimal-state-automata
number-of-states
0
votes
2
answers
30
NUMBER OF STATES IN DFA
asked
Nov 6, 2017
in
Theory of Computation
Parshu gate
624
views
finite-automata
theory-of-computation
number-of-states
Page:
1
2
next »
...