search
Log In

Recent questions tagged number-of-states

0 votes
2 answers
1
3 votes
2 answers
2
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
0 votes
2 answers
3
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
1 vote
1 answer
4
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
0 votes
0 answers
5
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
0 votes
0 answers
6
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
0 votes
1 answer
7
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
1 vote
0 answers
8
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
0 votes
1 answer
9
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
0 votes
1 answer
11
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
0 votes
1 answer
12
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
0 votes
1 answer
13
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
0 votes
0 answers
14
0 votes
3 answers
15
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
1 vote
1 answer
16
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
1 vote
1 answer
17
1 vote
0 answers
18
1 vote
2 answers
19
3 votes
2 answers
20
2 votes
0 answers
21
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
2 votes
1 answer
22
2 votes
2 answers
23
$ 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
0 votes
2 answers
26
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
1 vote
1 answer
27
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
1 vote
0 answers
28
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
2 votes
1 answer
29
...