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
1
answer
1
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
18 hours
ago
in
Theory of Computation
by
Mizuki
Junior
(
987
points)

23
views
finiteautomata
theoryofcomputation
minimalstateautomata
nfa
0
votes
0
answers
2
Self Doubt
I tried to draw DFA for  string w such that there are even a's and every a is followed by at least one b. First I took two dfa's one for even no of a's and other for strings where every a is followed by atleast one b and took their intersection ... there is a solution online for the same problem with 5 states. So, DFA obtained via intersection of two DFA's doesn't ensure minimal DFA ?
asked
2 days
ago
in
Theory of Computation
by
Jeevesh
(
229
points)

19
views
theoryofcomputation
finiteautomata
0
votes
1
answer
3
Introduction to computer theory
What should be the approach to draw the DFA  "All strings that have exactly one double letter in them" on symbols {a,b}.
asked
3 days
ago
in
Theory of Computation
by
Jeevesh
(
229
points)

43
views
theoryofcomputation
finiteautomata
dpda
0
votes
1
answer
4
GATEBOOK2019TOC15
$M_1$ and $M_2$ are 2 minimal DFAs containing $n_1$ and $n_2$ number of states $(n_1 \neq n_2).$ Which of the following statements is true? $M_1$ and $M_2$ can represent the same language If $n_1 > n_2,$ $L(M_1) \supset L(M_2)$ If $n_1 > n_2,$ $L(M_1) \subset L(M_2)$ None of the above
asked
3 days
ago
in
Theory of Computation
by
GATEBOOK
Active
(
1.7k
points)

18
views
gb2019toc1
finiteautomata
0
votes
1
answer
5
States in DFA
If NFA has 'n' states then how DFA can have 2^n states. Please help me in understanding how this is true. As per my understanding every DFA is NFA then how no of states can be more in DFA than nfa Please suggest Thanks
asked
5 days
ago
in
Theory of Computation
by
Mayankprakash
Junior
(
727
points)

22
views
numberofstates
finiteautomata
theoryofcomputation
+1
vote
1
answer
6
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
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
1.4k
points)

94
views
finiteautomata
minimalstateautomata
numberofstates
0
votes
0
answers
7
RE for given FA
The correct regular expression for the below mentioned Finite Automata Do we have to have ca* as C is dead state,does dead state be a part of regular expression? The expression I am gettting is c*a(d*+ba*) as C state is dead state hence no need to consider it.Please Correct me.
asked
Nov 6
in
Theory of Computation
by
sripo
Junior
(
717
points)

26
views
theoryofcomputation
finiteautomata
regularexpressions
regularlanguages
+1
vote
1
answer
8
What is the minimal DFA for this language (11+111)*, for Σ={0,1}.
asked
Nov 6
in
Theory of Computation
by
sripo
Junior
(
717
points)

34
views
theoryofcomputation
minimalstateautomata
regularexpressions
finiteautomata
nfa
0
votes
0
answers
9
Number of substrings for a given sub string having repeated symbols
asked
Nov 5
in
Theory of Computation
by
sripo
Junior
(
717
points)

36
views
permutationsandcombinations
counting
theoryofcomputation
algorithms
finiteautomata
0
votes
1
answer
10
Finite Automata
asked
Nov 3
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

37
views
finiteautomata
theoryofcomputation
nfa
+1
vote
1
answer
11
Gateforum Test Series
If NFA contains n states, then the equivalent minimized DFA in best case will contain how many states? A. 0 B. n C. 1 D. (n1)
asked
Oct 31
in
Theory of Computation
by
Gupta731
Active
(
1.5k
points)

36
views
gateforumtestseries
theoryofcomputation
finiteautomata
0
votes
1
answer
12
Regular Language and Ambiguity
For every regular grammar, we can always have an unambigious grammar?
asked
Oct 29
in
Theory of Computation
by
smsubham
Loyal
(
8.1k
points)

33
views
theoryofcomputation
finiteautomata
regularlanguages
inherentlyambiguous
0
votes
1
answer
13
Acebook
The minimal finite automata accepting the strings in r=0*1* has ________ states? for DFA its 3 states and for NFA its 2 states which one should i go with?
asked
Oct 21
in
Theory of Computation
by
abhishek1995_cse
(
155
points)

45
views
finiteautomata
regularexpressions
0
votes
1
answer
14
Does ambiguity problem is decidable for regular grammar(right linear grammar)?
asked
Oct 20
in
Theory of Computation
by
sandyoverflow
(
19
points)

37
views
theoryofcomputation
finiteautomata
0
votes
0
answers
15
Finite Automata
asked
Oct 18
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
899
points)

50
views
finiteautomata
theoryofcomputation
minimalstateautomata
regularexpressions
0
votes
2
answers
16
TOC Regular Langauges
Is L= 0n1 n>=0 regular? Is the kleene closure i.e. (L)* regular?
asked
Oct 18
in
Theory of Computation
by
sakharam
Active
(
2.4k
points)

160
views
regularlanguages
theoryofcomputation
finiteautomata
0
votes
0
answers
17
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
in
Theory of Computation
by
sripo
Junior
(
717
points)

25
views
minimalstateautomata
theoryofcomputation
finiteautomata
numberofstates
theoryofcomputation_
0
votes
0
answers
18
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
in
Theory of Computation
by
sripo
Junior
(
717
points)

33
views
minimalstateautomata
theoryofcomputation
finiteautomata
nondeterminism
0
votes
0
answers
19
To test if the given language is regular.
asked
Oct 16
in
Theory of Computation
by
sripo
Junior
(
717
points)

69
views
regularexpressions
regularlanguages
finiteautomata
theoryofcomputation
gate2019preparation
0
votes
0
answers
20
Can a^p where p is a prime number be an NFA?
asked
Oct 16
in
Theory of Computation
by
sripo
Junior
(
717
points)

68
views
theoryofcomputation
finiteautomata
nfa
#dfa
regularlanguages
regularexpressions
0
votes
0
answers
21
Regular Languages
Which is the equivalent Regular Expression for the following: "Strings in which every group of 3 symbols should contain atleast 1 a." a)[(a+b) (a+b)a]* b) [(a+b) (a+b)a]* [(a+b)(a+b)a]* c)[(ϵ + b + bb)a]* [ ϵ+ b + bb] d) (abb)* (bab)b* (bba)*
asked
Oct 14
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
899
points)

38
views
theoryofcomputation
regularlanguages
regularexpressions
finiteautomata
0
votes
1
answer
22
Formal Languages
If G= ({S} , {a}, {S>SS} , S), then language L(G) is a)ϕ b)aa(a)* c)(aa)* d)None of these
asked
Oct 14
in
Theory of Computation
by
Sambhrant Maurya
Junior
(
899
points)

42
views
theoryofcomputation
finiteautomata
grammar
0
votes
0
answers
23
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
in
Theory of Computation
by
sripo
Junior
(
717
points)

33
views
theoryofcomputation
finiteautomata
regulargrammar
numberofdfa
minimalstateautomata
+1
vote
0
answers
24
Subset of a regular language
Let L be a regular language over {a,b}, Suppose a new language defined as follows, L = x1 , x2, x3, x4,........ L1 = x5, x10, x15 ..... L1 is defined as taking every string which is at positon 5, 10, 15 and so on, in other words, the positions that can be divided by 5. Is L1 regular?
asked
Oct 13
in
Theory of Computation
by
AnilGoudar
Active
(
4.6k
points)

18
views
theoryofcomputation
regularlanguages
discretemathematics
finiteautomata
0
votes
0
answers
25
TOC : Minimum State in Finite Automata ( virtualgate )
asked
Oct 12
in
Theory of Computation
by
arya_stark
Junior
(
501
points)

25
views
theoryofcomputation
finiteautomata
minimalstateautomata
numberofstates
0
votes
1
answer
26
Automata for given Regular Expression
Can you please draw the DFA for given regex (ab*)*
asked
Oct 10
in
Theory of Computation
by
sripo
Junior
(
717
points)

54
views
theoryofcomputation
regularexpressions
finiteautomata
regularlanguages
expression
Page:
1
2
3
4
5
6
...
19
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
Basic LaTeX guide
IIT Madras Phd
Databases GO Classroom
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
No issue, and quicklatex is useful.
Oh, I didn't notice that post. Should I let this...
A bit more specific guide for GO can be found...
You can give the solution  most of the...
belated happist birthday Arjun sir .
42,416
questions
48,474
answers
154,487
comments
62,893
users