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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
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 finiteautomata
Some useful problems
+1
vote
0
answers
1
self doubt
is it necessary for the gate exam that minimisation of dfa can be solved by partitiong method ?? will it be safe to escape partitining method and problem can be solved by table filling method??
asked
Jul 18
in
Theory of Computation
by
vijju532
Junior
(
679
points)

46
views
theoryofcomputation
finiteautomata
nfa
0
votes
2
answers
2
Doubt Regular Language and regular expressions
asked
Jul 16
in
Theory of Computation
by
abhiram144
(
63
points)

108
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
0
votes
1
answer
3
GATE  TOC Regular Languages & FA
Let L(r1)=(b*ab*ab*ab*)* & L(r2)=(b*ab*ab*)*. What is L(r1) Intersection L(r2)? a) (b*ab*ab*ab*)* b) (b*ab*ab*)* c) (b*ab*ab*)^6 d) (b*ab*ab*ab*ab*ab*ab*)* Please do explain also.
asked
Jul 15
in
Theory of Computation
by
Ashish Roy 1
(
111
points)

108
views
theoryofcomputation
regularlanguages
regularexpressions
finiteautomata
0
votes
2
answers
4
UGCNETJuly2018II31
Two finite state machines are said to be equivalent if they: Have the same number of edges Have the same number of states Recognize the same set of tokens Have the same number of states and edges
asked
Jul 13
in
Theory of Computation
by
Pooja Khatri
Active
(
5.1k
points)

471
views
ugcnetjuly2018ii
theoryofcomputation
finiteautomata
0
votes
1
answer
5
UGCNETJuly2018II32
The finite state machine given in figure below recognizes: anu string of odd number of a's anu string of odd number of b's any string of even number of a's and odd number of b's any string of odd number of a's and odd number of b's
asked
Jul 13
in
Theory of Computation
by
Pooja Khatri
Active
(
5.1k
points)

166
views
ugcnetjuly2018ii
theoryofcomputation
finiteautomata
0
votes
1
answer
6
minimum finite automata
construct the minimul FA, that accepts all the string of 0's and 1's A)The second symbol from the right end of the string is 0 B)The third symbol from the right end of the string is 1
asked
Jul 10
in
Theory of Computation
by
suraj patel
(
71
points)

67
views
finiteautomata
theoryofcomputation
minimalstateautomata
0
votes
1
answer
7
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
in
Theory of Computation
by
suraj patel
(
71
points)

135
views
finiteautomata
theoryofcomputation
minimalstateautomata
numberofstates
0
votes
1
answer
8
Peter Linz Chapter 2 finite automata Definition 2.5 NFA
asked
Jul 9
in
Theory of Computation
by
swpril
(
55
points)

84
views
theoryofcomputation
finiteautomata
peterlinz
nfa
0
votes
1
answer
9
Chapter 2 An introduction to formal languages and automata peter linz
asked
Jul 8
in
Theory of Computation
by
swpril
(
55
points)

193
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
1
answer
10
Simplifying regular expressions
What is regex for the DFA: I am coming up with following two: 1. b*a(a+b)* and 2. b*a(b+ab*a)*+b*ab*a(ab*a+b)* Both seems to be correct to me. For X1, we have regex b*a(b+ab*a) For X2, we have regex b*ab*a(ab*a ... question: I want to know if I can simplify regex 2 to regex 1 by regex identities, but not by any other approach say by dfa minimization. Is it possible?
asked
Jul 1
in
Theory of Computation
by
GateAspirant999
Active
(
2.8k
points)

140
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
+2
votes
1
answer
11
Introduction to Formal Language, Fall 2017
asked
Jun 30
in
Theory of Computation
by
Apoorva Jain
(
227
points)

86
views
theoryofcomputation
regularlanguages
peterlinz
finiteautomata
grammar
0
votes
1
answer
12
#DFA #TOC #theoryofcomputation
How to construct an automata with even number of a's OR odd number of b's?
asked
Jun 24
in
Theory of Computation
by
aditykansara
(
17
points)

68
views
finiteautomata
theoryofcomputation
0
votes
0
answers
13
ISI CSB 2018 Question number C4.
C4. Construct a Deterministic Finite Automaton (DFA) to accept L={s1s2.....sn  n >=1; for each i=1,2,.....n, si € {0,1}, and the number of 1's minus the number of 0's in s1s2....si is zero,one or two} For example, the DFA should accept 11 or 1100 but not 1110.
asked
Jun 19
in
Theory of Computation
by
Anwesha Kashyap
(
13
points)

69
views
isi
finiteautomata
0
votes
1
answer
14
Decision properties of finite automata
Is equivalence problem decidable problem or not?
asked
Jun 15
in
Theory of Computation
by
Harshitha 123
(
99
points)

56
views
theoryofcomputation
finiteautomata
0
votes
0
answers
15
Theory of computation
What is grid automata (m+1)(n+1) state calculation? (For some question asked from Peter Linz unit 2 exercise 2(d) the answer is given as" it is like grid automata and to calculate number of states we can use (m+1)(n+1) if we require m a's and n b's" and the question is "all strings with at least one 'a' and exactly 2b's" )
asked
Jun 14
in
Theory of Computation
by
Harshitha 123
(
99
points)

57
views
finiteautomata
theoryofcomputation
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)
asked
Jun 12
in
Theory of Computation
by
Harshitha 123
(
99
points)

78
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
0
votes
1
answer
17
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
(
497
points)

116
views
usergate2018
usermod
finiteautomata
minimalstateautomata
0
votes
1
answer
18
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
(
201
points)

49
views
theoryofcomputation
finiteautomata
0
votes
1
answer
19
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
(
149
points)

231
views
finiteautomata
nfa
theoryofcomputation
0
votes
1
answer
20
Theory of computation
asked
Jun 6
in
Theory of Computation
by
Prince Sindhiya
Loyal
(
5.3k
points)

63
views
theoryofcomputation
finiteautomata
0
votes
1
answer
21
Toc NFa to DFA
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
Junior
(
743
points)

65
views
minimization
finiteautomata
0
votes
1
answer
22
Toc dfa
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
Junior
(
743
points)

57
views
finiteautomata
0
votes
2
answers
23
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
Junior
(
743
points)

139
views
theoryofcomputation
finiteautomata
minimalstateautomata
+1
vote
2
answers
24
Toc NFa
asked
Jun 5
in
Theory of Computation
by
Shivani gaikawad
Junior
(
743
points)

39
views
theoryofcomputation
nfa
minimalstateautomata
finiteautomata
0
votes
2
answers
25
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
Junior
(
743
points)

72
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
26
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
(
71
points)

96
views
theoryofcomputation
finiteautomata
0
votes
2
answers
27
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
(
71
points)

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

114
views
finiteautomata
theoryofcomputation
regularexpressions
nfa
0
votes
0
answers
29
FA to Regular Expression: when no two a's and no two b's should come together
asked
May 9
in
Theory of Computation
by
surbhijain93
(
131
points)

166
views
theoryofcomputation
regularexpressions
finiteautomata
Page:
« prev
1
2
3
4
5
6
7
8
9
...
20
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
IIT HYDERABAD M.Tech (RA) 3Years Winter Session Interview experience
INDIAN AIR FORCE
GATE BOOK _ TEST SERIES DOUBT_
Visualizing complex C code
GATE Book Test Series
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
First of all, congratulations!
I can...
Congrats man. You wrote gate in B.Tech 3rd year?
Thank You so much sir for giving tips. I will...
Please elucidate this really important...
44,312
questions
49,803
answers
164,509
comments
65,865
users