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 dfa
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
(
81
points)

24
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
0
votes
1
answer
2
KLP MISHRA
Given {L: every 'a' is followed by "bb"} Design a DFA for LATE(L) and TRUNCATE(L) LATE(L) is obtained by removing the first symbol from L and TRUNCATE(L) is obtained by removing the last symbol from L Eg: If L is 00(0+1)*01 then LATE(L) will be 0(0+1)*01 and TRUNCATE(L) would be 00(0+1)*0
asked
Jun 9
in
Theory of Computation
by
Sourav_35
(
199
points)

25
views
theoryofcomputation
dfa
0
votes
1
answer
3
Conversion of DFA to NFA
Q.) Given an arbitrary DFA with 2N states, what will be the number of states of the corresponding NFA? a) N x N b) 2N c) 2N d) N! Now, as we know that > no. of states in minimal DFA >= no. of states in NFA. So, anything less ... can be the answer but the answer which I found in the source is option (b) i.e 2N. Please suggest the proper explanation for this problem.
asked
Jun 9
in
Theory of Computation
by
garvit_vijai
(
7
points)

28
views
dfa
nfa
theoryofcomputation
0
votes
1
answer
4
Toc NFa to DFA
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
(
181
points)

30
views
minimization
dfa
0
votes
1
answer
5
Toc dfa
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
(
181
points)

43
views
dfa
0
votes
2
answers
6
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)

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

25
views
theoryofcomputation
nfa
minimalstateautomata
dfa
0
votes
2
answers
8
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)

45
views
theoryofcomputation
dfa
minimalstateautomata
0
votes
1
answer
9
deterministic finite automata
find the DFA which accept strings such that 2nd symbol from RHS is $'a'$ . $w=\{a,b\}^*$
asked
May 31
in
Theory of Computation
by
suraj patel
(
27
points)

52
views
theoryofcomputation
dfa
finiteautomata
0
votes
2
answers
10
peter linz
DFA For $L= \{w_1aw_2 : w_1 \geq 3, w_2 \leq 5\}$ where $\sum = \{a,b\}$
asked
May 30
in
Theory of Computation
by
suraj patel
(
27
points)

62
views
theoryofcomputation
dfa
0
votes
0
answers
11
what is the regular expression and design dfa and nfa for arthimatic expression
asked
May 13
in
Theory of Computation
by
doaa
(
31
points)

71
views
finiteautomata
theoryofcomputation
regularexpressions
dfa
nfa
0
votes
2
answers
12
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)

90
views
theoryofcomputation
minimalstateautomata
finiteautomata
dfa
numberofstates
+1
vote
1
answer
13
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
+1
vote
0
answers
14
Peter linz
how to draw dfa for this? L= {w: there are at most two runs of a’s of length three}.
asked
May 3
in
Theory of Computation
by
Ananya Jaiswal 1
Active
(
1.6k
points)

65
views
theoryofcomputation
peterlinz
dfa
0
votes
1
answer
15
Regular expression
asked
Apr 10
in
Theory of Computation
by
Prince Sindhiya
Junior
(
637
points)

61
views
theoryofcomputation
dfa
+1
vote
1
answer
16
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)

113
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
dfa
0
votes
0
answers
17
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
in
Theory of Computation
by
smsubham
Loyal
(
6.2k
points)

76
views
theoryofcomputation
nfa
finiteautomata
dfa
numberofstates
+2
votes
1
answer
18
Time complexity to minimize Finite Automata
asked
Mar 27
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
6k
points)

93
views
theoryofcomputation
finiteautomata
dfa
nfa
0
votes
1
answer
19
Complementation of DFA
Complementation of DFA works for all DFA is it true ? Given DFA, a should be followed by a 'b', In the complementation of this DFA the string aab is getting accepted a is getting followed by a 'b'
asked
Mar 18
in
Theory of Computation
by
sanju77767
(
151
points)

70
views
dfa
theoryofcomputation
0
votes
2
answers
20
finite automata
Draw the DFA for (a*b +b*a)
asked
Mar 17
in
Theory of Computation
by
varunraj
Junior
(
667
points)

111
views
theoryofcomputation
dfa
finiteautomata
0
votes
1
answer
21
Self doubt
Is dead state necessary in minimal DFA?
asked
Mar 16
in
Theory of Computation
by
Mk Utkarsh
Boss
(
12.6k
points)

84
views
theoryofcomputation
dfa
0
votes
1
answer
22
THEORY OF COMPUTER SCIENCE BY KLP MISHRA
asked
Mar 16
in
Theory of Computation
by
Sourav_35
(
199
points)

76
views
theoryofcomputation
dfa
+2
votes
1
answer
23
#TOC Doubt  Regular expressions
Part A: Given : (bab*ab*)* How can it be interpreted as: 1.((b+ab*)ab*)* 2.(b+(ab*ab*))* 3.((b+a)b*ab*)* Part B: 1.What will be its NFA ? 2.Can we draw a direct MINIMAL DFA for such questions?
asked
Mar 13
in
Theory of Computation
by
ashishgateashish
(
93
points)

126
views
regularexpressions
finiteautomata
nfa
dfa
theoryofcomputation
+2
votes
1
answer
24
Finite Automata
What's is the meaning of the statement: An automatic is a cognitive device and a grammar is a generative device. What does the word cognitive and generative mean in this respect.
asked
Mar 10
in
Theory of Computation
by
hrcule
(
135
points)

52
views
theoryofcomputation
dfa
+1
vote
1
answer
25
test_series
Consider the DFA M : Number of distinct strings of length $3$ such that $\delta(q_{0},w) = q_{0}$ $10$ $14$ $18$ $20$
asked
Mar 7
in
Theory of Computation
by
shivanisrivarshini
Boss
(
14.1k
points)

80
views
theoryofcomputation
dfa
+1
vote
1
answer
26
Introduction to Computer Theory
Give Regular Expression for Language of all those strings which do not contain the substring ‘bb’. Also draw its DFA.
asked
Mar 5
in
Theory of Computation
by
The Capricorn
(
147
points)

58
views
dfa
theoryofcomputation
+1
vote
1
answer
27
Introduction to Computer Theory
Give Regular Expression for the Language of all those strings which end with ‘aa’ or ‘ab’ and have odd length. Also, draw its DFA.
asked
Mar 5
in
Theory of Computation
by
The Capricorn
(
147
points)

45
views
theoryofcomputation
dfa
+1
vote
1
answer
28
Introduction to computer theory
Draw a Finite Automata for the language of all strings which end with 'ab' and have even length.
asked
Mar 5
in
Theory of Computation
by
The Capricorn
(
147
points)

27
views
theoryofcomputation
dfa
+1
vote
2
answers
29
NFAE to DFA conversion. (which is the correct solution?)
asked
Feb 27
in
Theory of Computation
by
ashishgateashish
(
93
points)

336
views
theoryofcomputation
nfa
finiteautomata
dfa
numberofstates
0
votes
0
answers
30
Introduction to Computer Theory
build an FA such that when the labels a and b are swapped the new machine is different from the old one but equivalent (the language defined by these machines is the same)
asked
Feb 25
in
Theory of Computation
by
The Capricorn
(
147
points)

51
views
theoryofcomputation
dfa
Page:
1
2
3
4
5
6
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
The GATE journey
BARC Interview Experience 15th June 2018
COAP Admission and IITD, IITK Interview Experience 2018
MS Interview Experience at IITK
Effect of Academic/ Career Gap during Mtech Placements at IIT/NIT
Follow @csegate
Gatecse
Recent questions tagged dfa
Recent Blog Comments
Prepare for interviews from the date of GATE ...
@ krishn.jh I started my first revision in ...
Congrates @
Inspiring!!!
Thank you :)
36,088
questions
43,532
answers
123,706
comments
42,762
users