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 finiteautomata
Some useful problems
0
votes
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
5 days
ago
in
Theory of Computation
by
vijju532
(
297
points)

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

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

57
views
theoryofcomputation
regularlanguages
regularexpressions
finiteautomata
0
votes
1
answer
4
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
(
59
points)

36
views
finiteautomata
theoryofcomputation
minimalstateautomata
0
votes
1
answer
5
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
(
59
points)

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

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

90
views
theoryofcomputation
peterlinz
finiteautomata
0
votes
1
answer
8
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.6k
points)

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

48
views
theoryofcomputation
regularlanguages
peterlinz
finiteautomata
grammar
0
votes
1
answer
10
#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)

47
views
finiteautomata
theoryofcomputation
0
votes
0
answers
11
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)

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

40
views
theoryofcomputation
finiteautomata
0
votes
0
answers
13
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
(
95
points)

42
views
finiteautomata
theoryofcomputation
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
in
Theory of Computation
by
Harshitha 123
(
95
points)

56
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
0
votes
1
answer
15
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
(
451
points)

90
views
usergate2018
usermod
finiteautomata
minimalstateautomata
0
votes
1
answer
16
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)

34
views
theoryofcomputation
finiteautomata
0
votes
1
answer
17
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
(
11
points)

56
views
finiteautomata
nfa
theoryofcomputation
0
votes
1
answer
18
Theory of computation
asked
Jun 6
in
Theory of Computation
by
Prince Sindhiya
Active
(
1.2k
points)

52
views
theoryofcomputation
finiteautomata
0
votes
1
answer
19
Toc NFa to DFA
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
(
197
points)

50
views
minimization
finiteautomata
0
votes
1
answer
20
Toc dfa
asked
Jun 6
in
Theory of Computation
by
Shivani gaikawad
(
197
points)

46
views
finiteautomata
0
votes
2
answers
21
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
(
197
points)

120
views
theoryofcomputation
finiteautomata
minimalstateautomata
+1
vote
2
answers
22
Toc NFa
asked
Jun 5
in
Theory of Computation
by
Shivani gaikawad
(
197
points)

30
views
theoryofcomputation
nfa
minimalstateautomata
finiteautomata
0
votes
2
answers
23
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
(
197
points)

60
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
24
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
(
59
points)

61
views
theoryofcomputation
finiteautomata
0
votes
2
answers
25
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
(
59
points)

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

89
views
finiteautomata
theoryofcomputation
regularexpressions
nfa
0
votes
0
answers
27
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
(
61
points)

102
views
theoryofcomputation
regularexpressions
finiteautomata
0
votes
2
answers
28
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)

114
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
+1
vote
1
answer
29
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)

77
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
Page:
1
2
3
4
5
6
...
17
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
AAI Junior Exceutive(Information Technology)
The 2018 APL Problem Solving Contest
GO Classroom for GATE 2019
Mtech CSE  IITH (TA) Interview Experience
MS Programme @ IIT
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
Why can't I able to edit my profile in GO ...
Glad to know that..
Today. You should get tracking mail by tomorrow.
What about my order sir, when will it be shipped??
Will be sent by tomorrow.
37,183
questions
44,756
answers
127,494
comments
43,817
users