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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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 minimalstateautomata
0
votes
0
answers
1
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
in
Theory of Computation
by
Harshitha 123
(
87
points)

28
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
0
votes
1
answer
2
GATE CS Mock 2018 (Set 2)
Let δ denote the transition function and α denoted the extended transition function of the εNFA whose transition table is given below: Which of the following option is correct? A) α (q1,aba) is {q0, q2} B) null reachable states are {q0, q1, q2}B C) α (q3,bab) is {q0, q1, q2, q3} D) None of these
asked
Jun 11
in
Theory of Computation
by
Nikhil Patil
(
365
points)

73
views
usergate2018
usermod
finiteautomata
minimalstateautomata
0
votes
2
answers
3
Toc DFA
asked
Jun 6
in
Theory of Computation
by
Prince Sindhiya
Junior
(
685
points)

64
views
minimalstateautomata
0
votes
2
answers
4
Toc dfa
The minimum number of state in the DFA for the language $L = \{ w \mid (n_a(w)+2n_b(w))mod \hspace{0.1cm} 3<2 \} $ is
asked
Jun 5
in
Theory of Computation
by
Shivani gaikawad
(
181
points)

104
views
theoryofcomputation
dfa
minimalstateautomata
+1
vote
2
answers
5
Toc NFa
asked
Jun 5
in
Theory of Computation
by
Shivani gaikawad
(
181
points)

26
views
theoryofcomputation
nfa
minimalstateautomata
dfa
0
votes
2
answers
6
Toc DFA
The minimum number of state in the DFA for the language $L = \{ w \mid w \in \{a,b\}^* \text{ w has exactly two a's and at least two b's} \}$ is $9$ $10$ $16$ None
asked
Jun 5
in
Theory of Computation
by
Shivani gaikawad
(
181
points)

46
views
theoryofcomputation
dfa
minimalstateautomata
0
votes
2
answers
7
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
in
Theory of Computation
by
kislaya Pant
(
165
points)

92
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
+1
vote
1
answer
8
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
in
Theory of Computation
by
kislaya Pant
(
165
points)

70
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
1
answer
9
Automata (How to create DFA for the language)
asked
May 6
in
Theory of Computation
by
kislaya Pant
(
165
points)

65
views
theoryofcomputation
minimalstateautomata
finiteautomata
+1
vote
1
answer
10
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
in
Theory of Computation
by
smsubham
Loyal
(
6.2k
points)

114
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
0
answers
11
Minimization of FSM
Is minimization of Finite State Machine(FSM) based on Dynamic Programming(DP) paradigm ? If yes , then what should be the optimal substructure and overlapping subproblems ?
asked
Feb 25
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
6k
points)

86
views
theoryofcomputation
finiteautomata
minimalstateautomata
+6
votes
2
answers
12
GATE20186
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true? $k \geq 2^n$ $k \geq n$ $k \leq n^2$ $k \leq 2^n$
asked
Feb 14
in
Theory of Computation
by
gatecse
Boss
(
18k
points)

1.2k
views
gate2018
theoryofcomputation
minimalstateautomata
normal
0
votes
1
answer
13
Minimal DFA
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____ My ans : 4 states given ans : 5 states
asked
Jan 31
in
Theory of Computation
by
Anjan
Active
(
1.7k
points)

147
views
theoryofcomputation
minimalstateautomata
+2
votes
2
answers
14
How many states in finite automata for the expression L={a^n, where n is a finite number}.
asked
Jan 28
in
Theory of Computation
by
Jayant Isswani
(
67
points)

139
views
finiteautomata
minimalstateautomata
theoryofcomputation
+2
votes
0
answers
15
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
in
Theory of Computation
by
junk_mayavi
Active
(
3.9k
points)

47
views
theoryofcomputation
minimalstateautomata
numberofstates
+2
votes
1
answer
16
#states DFA
The minimum no of states required to construct a DFA accepting the language of binary strings which contain an equal no of (01) and (10) is
asked
Dec 31, 2017
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
7.9k
points)

152
views
theoryofcomputation
dfa
finiteautomata
minimalstateautomata
+1
vote
1
answer
17
MINIMAL DFA
asked
Dec 31, 2017
in
Theory of Computation
by
Aakanchha
Junior
(
727
points)

125
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
0
votes
0
answers
18
[Madeasy] the minimum number of states in DFA for given language
asked
Dec 20, 2017
in
Theory of Computation
by
techbrk3
(
481
points)

81
views
minimalstateautomata
0
votes
0
answers
19
No of states in Min DFA
No of states in Min DFA, that accepts (1)* over {0,1} alphabets is 1 states 2 states None of these
asked
Dec 17, 2017
in
Theory of Computation
by
hacker16
Active
(
2.7k
points)

41
views
minimalstateautomata
theoryofcomputation
0
votes
1
answer
20
minimal Dfa
asked
Dec 3, 2017
in
Theory of Computation
by
Parshu gate
Active
(
4.9k
points)

67
views
numberofstates
minimalstateautomata
theoryofcomputation
+2
votes
2
answers
21
DFA no of states
What is the min no. of states required in DFA which accepts all strings starting with 1 and whose decimal value is divisible by 7?
asked
Dec 1, 2017
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
7.9k
points)

152
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
+1
vote
1
answer
22
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
(
937
points)

136
views
theoryofcomputation
minimalstateautomata
dfa
finiteautomata
numberofstates
+2
votes
0
answers
23
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
(
24.1k
points)

154
views
theoryofcomputation
dfa
minimalstateautomata
finiteautomata
numberofstates
+1
vote
2
answers
24
Number of states in a minimal DFA construction
asked
Nov 2, 2017
in
Theory of Computation
by
humblefool
Junior
(
937
points)

180
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
+1
vote
0
answers
25
Minimized DFA
What is the number of states in a minimal DFA accepting the language which contains all strings that either begin or end (or both) with 01 ? Assume alphabet set as {0,1} I got the answer but it was time consuming. Any hack on drawing its intuitive NFA ? as then conversion would be easier from NFA to DFA.
asked
Oct 31, 2017
in
Theory of Computation
by
just_bhavana
Boss
(
11.9k
points)

72
views
minimalstateautomata
+5
votes
2
answers
26
How to make a minimal DFA
Draw a minimal DFA which accepts a language L over {a,b} 01 [ ((10) * + 111) * + 0 ] * 1
asked
Oct 26, 2017
in
Theory of Computation
by
ashwina
Active
(
1.9k
points)

93
views
theoryofcomputation
minimalstateautomata
+1
vote
0
answers
27
DFA minimization
Given : DFA. Minimum number of states required to construct an equivalent NFA is a)2 b)3 c)4 d)6 PS: how can we minimize if initial and final states of DFAare not given ?
asked
Oct 24, 2017
in
Theory of Computation
by
shaurya vardhan
Active
(
2.2k
points)

263
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
+4
votes
3
answers
28
TOC: Number of states in minimum DFA
I think, there will be 4 states in minimum DFA, following states will be merged in the resulted DFA {q0&q3}, {q4&q5}, {q1&q6}, {q2&q7}
asked
Oct 10, 2017
in
Theory of Computation
by
Manu Thakur
Boss
(
39.6k
points)

189
views
minimalstateautomata
theoryofcomputation
dfa
+1
vote
1
answer
29
Theoryofcomputation DFA
Design a minimal DFA accepting L={w ; atleast one 'a' in w is not immediately followed by 'b'}
asked
Oct 3, 2017
in
Theory of Computation
by
MayankSharma
(
143
points)

123
views
theoryofcomputation
dfa
minimalstateautomata
finiteautomata
0
votes
2
answers
30
Deterministic finite Automata
Can anyone help me out to draw a transition diagram for a DFA which accepts the set of strings in which 3rd symbol from RHS is 'a', Σ = {a,b} ??
asked
Oct 2, 2017
in
Theory of Computation
by
himu243
(
7
points)

111
views
dfa
theoryofcomputation
finiteautomata
minimalstateautomata
Page:
1
2
3
4
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
ALGORITHMS CHECKLIST:
A Failure who got into IISc
ISRO written test results are out!!
UGC NET 2018 Admit Card available for Download
IIIT Hyderabad Interview Experience
Follow @csegate
Gatecse
Recent questions tagged minimalstateautomata
Recent Blog Comments
Congrats :)
Next week everyone should get the address ...
Really man...very inspirational.. ...
Thank you everyone for showing your ...
I have seen a lot of failure stories but ur story ...
36,164
questions
43,621
answers
124,008
comments
42,881
users