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
+1
vote
0
answers
1
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
(
7.9k
points)

98
views
theoryofcomputation
nfa
finiteautomata
numberofstates
+1
vote
1
answer
2
#toc #peterlinz #nfa
Also is this nfa possible with less than three states??
asked
Apr 7
in
Theory of Computation
by
meghna
Active
(
1.6k
points)

100
views
finiteautomata
nfa
theoryofcomputation
+1
vote
3
answers
3
Regular Grammars
$S\rightarrow AB$ $A\rightarrow a$ $B\rightarrow b$ The language generated by the above grammar is ab and since we can give a FA for the language then it must be a regular language.Now,since the given grammar generates a regular language then it must be a regular ... but again it is not in the form of TYPE 3 or regular grammar,then how to identify if the grammar is regular or not?
asked
Apr 6
in
Theory of Computation
by
Sourav_35
(
201
points)

81
views
regulargrammar
theoryofcomputation
finiteautomata
+2
votes
1
answer
4
Time complexity to minimize Finite Automata
asked
Mar 27
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
7.6k
points)

133
views
theoryofcomputation
finiteautomata
nfa
0
votes
1
answer
5
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
(
275
points)

81
views
finiteautomata
theoryofcomputation
0
votes
2
answers
6
finite automata
Draw the DFA for (a*b +b*a)
asked
Mar 17
in
Theory of Computation
by
varunraj
Junior
(
727
points)

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

89
views
theoryofcomputation
finiteautomata
0
votes
1
answer
8
THEORY OF COMPUTER SCIENCE BY KLP MISHRA
asked
Mar 16
in
Theory of Computation
by
Sourav_35
(
201
points)

82
views
theoryofcomputation
finiteautomata
+2
votes
1
answer
9
#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)

149
views
regularexpressions
finiteautomata
nfa
theoryofcomputation
+1
vote
0
answers
10
Dfa to regex
please verify the regex
asked
Mar 12
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.6k
points)

68
views
theoryofcomputation
finiteautomata
regularexpressions
+1
vote
1
answer
11
Automata
If $L1$ is regular language and $L2$ is unknown language then what can we say about $L1L2$. Will it be regular or not? I think it will be regular because even if $L2$ is not regular then still (Regular  not Regular) will result in Regular, according to the properties of set ... from The given set will not change the set. I want to know if I am right and if I am not then what's the error?
asked
Mar 10
in
Theory of Computation
by
hrcule
(
287
points)

67
views
theoryofcomputation
regularlanguages
finiteautomata
+2
votes
1
answer
12
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
(
287
points)

69
views
theoryofcomputation
finiteautomata
+1
vote
1
answer
13
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.2k
points)

83
views
theoryofcomputation
finiteautomata
+1
vote
1
answer
14
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)

64
views
finiteautomata
theoryofcomputation
+1
vote
1
answer
15
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)

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

32
views
theoryofcomputation
finiteautomata
+1
vote
0
answers
17
Peter linz exercise 2.1
$\sum = \left \{ a,b \right \}$ Is it possible to create DFA for given language with less than 10 states? L = $\left \{ w: \left  w \right  mod 3 = 0, \left w \right  \neq 6 \right \}$
asked
Mar 4
in
Theory of Computation
by
Mk Utkarsh
Boss
(
19.6k
points)

95
views
theoryofcomputation
finiteautomata
+1
vote
0
answers
18
Regular Expression
What is the regular expression of $L = \{ s \in L$ $i$ = no of $1$ in string $s$ $j$ = no of $0$ in string $s$ $i+j$ is odd $\}$ ???
asked
Mar 4
in
Theory of Computation
by
Dharmesh Gusai
(
19
points)

100
views
regularexpressions
theoryofcomputation
finiteautomata
regularlanguages
+1
vote
1
answer
19
Language accepted by given NFA
Language accepted by following NFA and number of states in DFA accepting that Language are: $\{a^nn=2k,kϵN\}$ and 2 $\{a^{2n}n=2k,kϵN\}$ and 2 $\{a^nn=2k,kϵ N\}$ and 3 $\{a^{2n}n=2k,kϵ N\}$ and 3
asked
Mar 2
in
Theory of Computation
by
GateAspirant999
Active
(
2.7k
points)

60
views
finiteautomata
nondeterminism
theoryofcomputation
+2
votes
1
answer
20
Regular language Prefix
Given FSA for language L, how to find FSA that accepts all prefixes of L? Acc to below mentioned link "We can construct a DFA to decide Prefix(L) by taking the DFA for L and marking all states from which an accept state is reachable ... states from which an accept state is reachable as accept states, then eventually all states would turn to final states.Am I right?
asked
Mar 2
in
Theory of Computation
by
Mamta Satywali
Active
(
2.3k
points)

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

386
views
theoryofcomputation
nfa
finiteautomata
numberofstates
0
votes
0
answers
22
Minimization of FSM
Is minimization of Finite State Machine(FSM) based on Dynamic Programming(DP) paradigm ? If yes , then what should be the optimal substructure and overlapping subproblems ?
asked
Feb 25
in
Theory of Computation
by
ankitgupta.1729
Loyal
(
7.6k
points)

97
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
0
answers
23
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)

52
views
theoryofcomputation
finiteautomata
0
votes
1
answer
24
Introduction to Computer Theory
build a machine that accepts all strings that have an even length that is not divisible by 6
asked
Feb 25
in
Theory of Computation
by
The Capricorn
(
147
points)

44
views
theoryofcomputation
finiteautomata
0
votes
1
answer
25
TOC *** test series FA
question seems to be easy. but could not understand the solution
asked
Feb 11
in
Theory of Computation
by
Moin Mukhtar
(
271
points)

134
views
theoryofcomputation
finiteautomata
testseries
0
votes
1
answer
26
DFA doubt!!
Is the following DFA valid ?? Can we go to same state from a same state with different inputs ??
asked
Feb 11
in
Theory of Computation
by
Bhumika Gupta
(
7
points)

62
views
finiteautomata
gate
+2
votes
1
answer
27
Regular Language
Let $L\mid$ be a regular language and $L_1 = \{x\mid\text{there exist y}\mid \text{so that xy} \in L \text{ and} \mid x \mid = 2 \mid y\mid \mid \}$ $L_2 = \{x\mid\text{there exist y}\mid \text{so that yx} \in L \text{ and} \mid x ... is regular but $L_2$ is not. $L_2$ is regular but $L_1$ is not. Both $L_1$ and $L_2$ are regular. Both $L_1$ and $L_2$ are not regular.
asked
Feb 2
in
Theory of Computation
by
vijay_jr
Active
(
1.1k
points)

88
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
0
answers
28
#TOC Doubt
L = anbm / n,m>=1 What type pf Language is this? Also, please tell are n,m are independent or dependent i.e can we have like n=2 and m=3 or both n,m have to have same values!?
asked
Jan 30
in
Theory of Computation
by
iarnav
Loyal
(
8.6k
points)

54
views
theoryofcomputation
finiteautomata
regularexpressions
regulargrammar
+2
votes
2
answers
29
How many states in finite automata for the expression L={a^n, where n is a finite number}.
asked
Jan 28
in
Theory of Computation
by
Jayant Isswani
(
67
points)

174
views
finiteautomata
minimalstateautomata
theoryofcomputation
+4
votes
0
answers
30
Self doubt
Which of the following statement TRUE & also EXPLAIN WHY... (1) "Power of Turing Machine is Equal to Power of DFA with 2 Stack" (2) "Power of Turing Machine is Equal to Power of DFA with 2 Counter" (3) "Power of Push Down Automata is Equal ... DFA with 1 stack <= DFA with 2 counter <= DFA with 2 stack } (6) Power of Stack is More than power of Counter
asked
Jan 22
in
Theory of Computation
by
Harsh Mehta
Active
(
1.3k
points)

48
views
theoryofcomputation
turingmachine
pushdownautomata
finiteautomata
Page:
« prev
1
2
3
4
5
6
7
8
9
...
18
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
syllabus of Statistics
List of Available Exams
New Assignment on Network programming : P2P simulation
Theory of Computation  GO Classroom
Probability  GO Classroom
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
@IITDELHIVISHAL Yes, it will work. Make your...
sir if watch& making notes from quality videos...
yes! those will be available on GO,no need to pay
did you mean, those tests also available in GO?
It's a test series conducted by Kiran sir i.e...
40,807
questions
47,492
answers
145,714
comments
62,249
users