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

I forgot my password
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
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 minimalstateautomata
+1
vote
2
answers
1
UGCNETJune2019II75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
416k
points)

67
views
ugcnetjune2019ii
finiteautomata
minimalstateautomata
+2
votes
3
answers
2
GATE201948
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
416k
points)

2.8k
views
gate2019
numericalanswers
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
3
Self Doubt
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11.
asked
Jan 19
in
Theory of Computation
by
kumar.dilip
Active
(
5.1k
points)

58
views
#dfa
numberofdfa
minimalstateautomata
0
votes
0
answers
4
Testbook Test Series: Theory of Computation  Minimal State Automata
$Que$ The minimum number of states in the $NFA$ for the regular expression $(a + a(b + aa)*b)* a(b + aa)*a$ is ______. Approach ?
asked
Jan 6
in
Theory of Computation
by
Soumya29
Boss
(
15.7k
points)

87
views
testbooktestseries
theoryofcomputation
minimalstateautomata
0
votes
0
answers
5
[AppliedCourse Test] Min DFA of (a*b*) complement
The Minimum DFA that accepts the given language is ____ L = { w  w is any string not in a*b*}
asked
Jan 5
in
Theory of Computation
by
VikramRB
(
239
points)

128
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
6
Self doubt TOC DFA
Construct a minimal DFA which accepts set of all strings over {a,b}, such that $1)$Second symbol from $RHS$ should be $‘a’$ $2)$Third symbol from $RHS$ should be $‘a’$
asked
Dec 27, 2018
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
43.8k
points)

59
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
2
answers
7
Minimal DFA
Given following NFA find the minimal equivalent DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
3.9k
points)

115
views
theoryofcomputation
minimalstateautomata
numberofstates
finiteautomata
+3
votes
2
answers
8
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
(
3.9k
points)

70
views
theoryofcomputation
numberofstates
minimalstateautomata
0
votes
1
answer
9
Reversal of DFA doubt
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state
asked
Dec 10, 2018
in
Theory of Computation
by
aditi19
Active
(
3.9k
points)

121
views
theoryofcomputation
finiteautomata
#dfa
minimalstateautomata
+2
votes
0
answers
10
Can't understand the intution behind the shortcut
let the ∑ = {0,1} ===> strings possible are should be Binary strings. No.of States in Minimal DFA that accepts, Decimal( Binary String ) = 0 mod n in ACE coaching institute, i learned that For Decimal( Binary String ) = 0 mod n i) if n ... String ) = 0 mod x or 0 mod y neither x divides y nor y divides x either x is divides y or y divides x
asked
Nov 30, 2018
in
Theory of Computation
by
Shaik Masthan
Veteran
(
61.9k
points)

101
views
minimalstateautomata
regularlanguages
0
votes
1
answer
11
Finite Automata
When we convert a (minimal) NFA to DFA by subset construction method, is the DFA obtained always a minimal DFA? Please elaborate.
asked
Nov 15, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

72
views
finiteautomata
theoryofcomputation
minimalstateautomata
nfa
+2
votes
1
answer
12
GATEBOOK2019TOC11
Consider the DFA shown below: The number of states in the equivalent minimized DFA is ______
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
11.4k
points)

229
views
gb2019toc1
numericalanswers
minimalstateautomata
+1
vote
1
answer
13
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
Active
(
4.9k
points)

188
views
finiteautomata
minimalstateautomata
numberofstates
+1
vote
1
answer
14
What is the minimal DFA for this language (11+111)*, for Σ={0,1}.
What is the number of states for the above DFA,please draw NFA,DFA and minimised DFA for the same.Also won't the language not accept epsilon?
asked
Nov 6, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

244
views
theoryofcomputation
minimalstateautomata
regularexpressions
finiteautomata
nfa
0
votes
0
answers
15
Finite Automata
asked
Oct 18, 2018
in
Theory of Computation
by
Sambhrant Maurya
Active
(
2.4k
points)

77
views
finiteautomata
theoryofcomputation
minimalstateautomata
regularexpressions
0
votes
0
answers
16
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/gate2015152
asked
Oct 17, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

94
views
minimalstateautomata
theoryofcomputation
finiteautomata
numberofstates
theoryofcomputation_
0
votes
0
answers
17
Construct DFA for given Language
For the language which ends with 01 or 11 or 10 or 11 for $\sum$={0,1}* .Is dfa possible for this language?
asked
Oct 16, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

50
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
+1
vote
1
answer
18
Grammar to DFA Construction
For the given Grammar S>aAbB A>bCaS B>aCbS C>aBbA Construct DFA I am getting confused in understanding how to take the final state.
asked
Oct 13, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

78
views
theoryofcomputation
finiteautomata
regulargrammar
numberofdfa
minimalstateautomata
0
votes
0
answers
19
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)

60
views
theoryofcomputation
finiteautomata
minimalstateautomata
numberofstates
0
votes
1
answer
20
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
(
113k
points)

134
views
theoryofcomputation
minimalstateautomata
numberofstates
0
votes
1
answer
21
Test Series
What will be the minimum no. of states for DFA for the above NFA? Please explain.
asked
Sep 23, 2018
in
Theory of Computation
by
Subham Nagar
Active
(
1k
points)

48
views
#dfa
minimalstateautomata
0
votes
0
answers
22
Doubt in Automata
If two finite state machines M and N are isomorphic then M can be transformed to N by relabeling (a) the states alone (b) the edges alone (c) both the states and edges (d) none of the above
asked
Sep 16, 2018
in
Theory of Computation
by
goluabhinan
(
55
points)

156
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
23
Doubt in Finite Automata
Consider the following DFA D. The number of states in the minimization of D is __________.
asked
Sep 12, 2018
in
Theory of Computation
by
goluabhinan
(
55
points)

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

43
views
theoryofcomputation
minimalstateautomata
numberofstates
+1
vote
0
answers
25
Minimum number of States
Ans. 5
asked
Aug 30, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.6k
points)

79
views
minimalstateautomata
finiteautomata
theoryofcomputation
numberofstates
0
votes
0
answers
26
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, 2018
in
Theory of Computation
by
suraj patel
(
51
points)

104
views
finiteautomata
theoryofcomputation
minimalstateautomata
0
votes
1
answer
27
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)

148
views
finiteautomata
theoryofcomputation
minimalstateautomata
numberofstates
0
votes
0
answers
28
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)

88
views
theoryofcomputation
minimalstateautomata
finiteautomata
numberofstates
0
votes
1
answer
29
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, 2018
in
Theory of Computation
by
Nikhil Patil
(
489
points)

140
views
usergate2018
usermod
finiteautomata
minimalstateautomata
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged minimalstateautomata
Recent Blog Comments
Why no pay now option is showing , i wanted to...
Nah I just meant, maybe consignment no. was...
49,807
questions
54,730
answers
189,326
comments
79,941
users