Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged number-of-states
0
votes
1
answer
1
parsers and dfa construction
Hi, there my question is while constructing DFA for LL(1) or LR(0), or SLR (1). parsing I'm seeing different variants of DFA for the same problem set, and I'm not able to determine which is correct and which is not please help I'm providing a question ... S->dA/aB A->bA/c B->bB/c so first is this second is this which one is correct and why please ex
Hi, there my question is while constructing DFA for LL(1) or LR(0), or SLR (1). parsing I'm seeing different variants of DFA for the same problem set, and I'm not able to...
utkarsh2077
173
views
utkarsh2077
asked
Dec 4, 2023
Compiler Design
theory-of-computation
number-of-dfa
number-of-states
+
–
1
votes
1
answer
2
Minimal Finite Automata - Theory of Computation
Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts the given set is _____________? (kindly explain the approach to this problem)
Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts th...
stillhere
369
views
stillhere
asked
Sep 10, 2023
Theory of Computation
minimal-state-automata
finite-automata
theory-of-computation
number-of-states
+
–
0
votes
2
answers
3
DFA
on seeing a dfa how can we predict the number of states in it?
on seeing a dfa how can we predict the number of states in it?
Manuj_og
210
views
Manuj_og
asked
May 2, 2023
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
0
votes
1
answer
4
#GateAppliedCourse-DFA-EpsilonNFA
can we solve it with a minimum of 4 states?
can we solve it with a minimum of 4 states?
Dknights
317
views
Dknights
asked
Nov 19, 2022
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
0
votes
2
answers
5
Minimal DFA
Given following NFA find the minimal equivalent DFA
Given following NFAfind the minimal equivalent DFA
aditi19
1.5k
views
aditi19
asked
Dec 14, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
finite-automata
+
–
3
votes
4
answers
6
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 strin...
Devwritt
1.5k
views
Devwritt
asked
Dec 13, 2018
Theory of Computation
theory-of-computation
number-of-states
minimal-state-automata
+
–
0
votes
2
answers
7
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 c...
Mayankprakash
1.1k
views
Mayankprakash
asked
Nov 9, 2018
Theory of Computation
number-of-states
finite-automata
theory-of-computation
+
–
1
votes
1
answer
8
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=152.The minimum no of st...
Abhisek Tiwari 4
2.4k
views
Abhisek Tiwari 4
asked
Nov 6, 2018
Theory of Computation
finite-automata
minimal-state-automata
number-of-states
+
–
1
votes
0
answers
9
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 questi...
sripo
1.3k
views
sripo
asked
Oct 17, 2018
Theory of Computation
minimal-state-automata
theory-of-computation
finite-automata
number-of-states
theory-of-computation-
+
–
0
votes
0
answers
10
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...
arya_stark
365
views
arya_stark
asked
Oct 12, 2018
Theory of Computation
theory-of-computation
finite-automata
minimal-state-automata
number-of-states
+
–
0
votes
1
answer
11
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____...
srestha
1.3k
views
srestha
asked
Oct 6, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
+
–
1
votes
0
answers
12
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 pro...
Gate Fever
2.8k
views
Gate Fever
asked
Sep 21, 2018
Digital Logic
number-of-states
finite-automata
digital-circuits
+
–
0
votes
1
answer
13
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 }.
Na462
937
views
Na462
asked
Sep 10, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
+
–
1
votes
0
answers
14
Minimum number of States
Ans. 5
Ans. 5
Na462
1.3k
views
Na462
asked
Aug 30, 2018
Theory of Computation
minimal-state-automata
finite-automata
theory-of-computation
number-of-states
+
–
0
votes
1
answer
15
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 whereA)Every String start and end with Zero.B)Every string Start and end with Same Symbol.
suraj patel
2.5k
views
suraj patel
asked
Jul 10, 2018
Theory of Computation
finite-automata
theory-of-computation
minimal-state-automata
number-of-states
+
–
0
votes
0
answers
16
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)
Harshitha 123
402
views
Harshitha 123
asked
Jun 12, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
0
votes
3
answers
17
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 ...
kislaya Pant
3.1k
views
kislaya Pant
asked
May 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
1
answer
18
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)....
kislaya Pant
1.1k
views
kislaya Pant
asked
May 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
1
answer
19
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?
smsubham
2.6k
views
smsubham
asked
Apr 8, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
1
votes
0
answers
20
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?
smsubham
800
views
smsubham
asked
Apr 8, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
1
votes
2
answers
21
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.
ashishgateashish
2.4k
views
ashishgateashish
asked
Feb 27, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
3
votes
2
answers
22
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.
Sona Barman
2.3k
views
Sona Barman
asked
Jan 15, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
2
votes
0
answers
23
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 __________...
junk_mayavi
384
views
junk_mayavi
asked
Jan 15, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
+
–
2
votes
1
answer
24
Gate mock test
please explain answer given is 5
please explain answer given is 5
VIKRAM KASANA
778
views
VIKRAM KASANA
asked
Jan 4, 2018
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
2
votes
2
answers
25
#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$
Tuhin Dutta
441
views
Tuhin Dutta
asked
Dec 31, 2017
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
1
votes
1
answer
26
MINIMAL DFA
Aakanchha
640
views
Aakanchha
asked
Dec 31, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
0
votes
1
answer
27
minimal Dfa
Parshu gate
600
views
Parshu gate
asked
Dec 3, 2017
Theory of Computation
number-of-states
minimal-state-automata
theory-of-computation
+
–
0
votes
2
answers
28
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?
rahul sharma 5
1.0k
views
rahul sharma 5
asked
Nov 20, 2017
Theory of Computation
theory-of-computation
finite-automata
number-of-states
+
–
1
votes
1
answer
29
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....
humblefool
950
views
humblefool
asked
Nov 16, 2017
Theory of Computation
theory-of-computation
minimal-state-automata
finite-automata
number-of-states
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register