Recent questions tagged number-of-states

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 (5.2k points) | 140 views

+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?

asked Dec 13, 2018 in Theory of Computation by Devwritt Active (4.1k points) | 83 views

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

asked Nov 10, 2018 in Theory of Computation by Mayankprakash Active (1k points) | 99 views

+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 Loyal (5.2k points) | 242 views

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

asked Oct 17, 2018 in Theory of Computation by sripo Active (2.5k points) | 151 views

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.7k points) | 76 views

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 (119k points) | 146 views

+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.7k points) | 64 views

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 (7k points) | 48 views

+1 vote

0 answers

10

Minimum number of States
Ans. 5

asked Aug 30, 2018 in Theory of Computation by Na462 Loyal (7k points) | 90 views

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.7k points) | 91 views

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.7k points) | 27 views

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 (51 points) | 159 views

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 (85 points) | 99 views

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 (147 points) | 398 views

+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 (147 points) | 158 views

+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 Boss (11.5k points) | 212 views

+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 Boss (11.5k points) | 197 views

+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.

asked Feb 27, 2018 in Theory of Computation by ashishgateashish (83 points) | 592 views

+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) | 224 views

+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 ______________ ?

asked Jan 15, 2018 in Theory of Computation by junk_mayavi Active (4.2k points) | 58 views

+2 votes

1 answer

22

Gate mock test
please explain answer given is 5

asked Jan 4, 2018 in Theory of Computation by VIKRAM KASANA (483 points) | 228 views

+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 Boss (10.6k points) | 130 views

+1 vote

1 answer

24

MINIMAL DFA

asked Dec 31, 2017 in Theory of Computation by Aakanchha Junior (663 points) | 189 views

0 votes

1 answer

25

minimal Dfa

asked Dec 3, 2017 in Theory of Computation by Parshu gate Active (3.1k points) | 83 views

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 (25.6k points) | 189 views

+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 Junior (963 points) | 171 views

+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.3k points) | 262 views

+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 (25.6k points) | 204 views

0 votes

2 answers

30

NUMBER OF STATES IN DFA

asked Nov 6, 2017 in Theory of Computation by Parshu gate Active (3.1k points) | 192 views

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 questions tagged number-of-states

Recent Posts

Recent Blog Comments