The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook 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
0
votes
0
answers
1
theory of autometa
let M be a finite autometa .let M' denote the machine obtained by interchanging the final and non final state L(M) U L(M') =sigma* L(M) $\cap$ L(M') =$\Phi$ i am sure that 1st is true but for 2nd take an example so 2nd become false but given that both are true for DFA where i am doing mistake ??
asked
5 days
ago
in
Theory of Computation
by
Gurdeep Saini
Loyal
(
7.6k
points)

24
views
finiteautomata
theoryofcomputation
regularlanguages
regularexpressions
0
votes
0
answers
2
made easy mock1
let L={set of all strings over {0,1}* , containing 01 and 011 as the substring } number of states in the minimal DFA of L’ is? i’m getting 3. please confirm if you are getting 3 or 4.
asked
Jan 8
in
Theory of Computation
by
aambazinga
Active
(
2.7k
points)

57
views
theoryofcomputation
finiteautomata
0
votes
0
answers
3
[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
(
163
points)

82
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
4
Theory Of computation
How many maximum number of production rules are possible in regular grammar equivalent to a given n state DFA, over the input alphabet {a,b,c} where q1 is always the initial state? Answer: 6n + 1
asked
Jan 4
in
Theory of Computation
by
debanjan sarkar
Active
(
4.1k
points)

38
views
theoryofcomputation
finiteautomata
0
votes
0
answers
5
Theory Of Computation
How many Moore machines are possible with two states X and Y for the input alphabet {a,b} and output alphabet {0,1}, where X is always the initial state?
asked
Jan 4
in
Theory of Computation
by
debanjan sarkar
Active
(
4.1k
points)

83
views
theoryofcomputation
finiteautomata
0
votes
1
answer
6
Regular Expression Statements
Can anyone explain how S2 is false,I did not understand their logic.
asked
Jan 1
in
Theory of Computation
by
sripo
Active
(
1.3k
points)

49
views
regularexpressions
theoryofcomputation
finiteautomata
regularlanguages
expression
madeeasytestseries
0
votes
1
answer
7
Made easy test series
does did method always apply when the NFA has no choice , means the no of state in the DFA is 1 more then NFA ??
asked
Dec 29, 2018
in
Theory of Computation
by
Gurdeep Saini
Loyal
(
7.6k
points)

40
views
madeeasytestseries
theoryofcomputation
finiteautomata
0
votes
0
answers
8
Automata
Given a language L, define Li as follows: L0 = { ϵ } L^i = L ^(i1) , for all i > 0 The order of a language is defined as the smallest “x” such that Li and Lx = Lx1 Consider the language L1 (over alphabet {a,b} ) accepted by the following automata. The order of L1 is _________
asked
Dec 28, 2018
in
Theory of Computation
by
Parasporwal
(
7
points)

32
views
#theoryofcomputation
finiteautomata
0
votes
1
answer
9
made easy theory of computation regular expression
which one of the following regular expression describe the language over {a,b} consist of no pair of consecutive a’s? a. (b*abb*) (a+€) b. (b+ab)* (a+€) c. (b*abb*)*(a+€)+b* d. (b*ab*)*(a+€)+b*(a+€)
asked
Dec 28, 2018
in
Theory of Computation
by
Ram Swaroop
Active
(
1.3k
points)

53
views
regularexpressions
theoryofcomputation
finiteautomata
0
votes
1
answer
10
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
(
26.4k
points)

45
views
theoryofcomputation
finiteautomata
minimalstateautomata
0
votes
1
answer
11
NTA NET DEC2018 Q4
asked
Dec 25, 2018
in
Theory of Computation
by
Sanjay Sharma
Veteran
(
50.2k
points)

40
views
theoryofcomputation
finiteautomata
0
votes
0
answers
12
decidablilty
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If a language is an REL (recursive enumerable ... recursive or not *undecidable*. Hence, recursive languages should be undecidablewhich they are not! What is wrong with the above reasoning?
asked
Dec 25, 2018
in
Theory of Computation
by
rballiwal
Active
(
1.1k
points)

42
views
finiteautomata
turingmachine
0
votes
0
answers
13
#TOC Regular Language Is this a regular set?
WXW^R where W,X belongs to (0,1)* W^R is reverse of a string!
asked
Dec 22, 2018
in
Theory of Computation
by
iarnav
Loyal
(
9.4k
points)

47
views
theoryofcomputation
regularlanguages
finiteautomata
regularexpressions
0
votes
1
answer
14
selfdoubt
Give an example of DFA minimization where the initial state is final state and there are one or more final states
asked
Dec 22, 2018
in
Theory of Computation
by
ck
(
387
points)

49
views
finiteautomata
minimization
0
votes
1
answer
15
#madeeasy
asked
Dec 19, 2018
in
Theory of Computation
by
Ramij
(
305
points)

87
views
madeeasytestseries
theoryofcomputation
finiteautomata
0
votes
1
answer
16
UGC NET 2016
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes. pls give a detailed solution
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

55
views
#dfa
finiteautomata
equivalenceclasses
regularlanguages
regularexpressions
0
votes
2
answers
17
DFA doubt
DFA in which 01 and 10 have equal number of occurrences
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

128
views
finiteautomata
theoryofcomputation
#dfa
0
votes
2
answers
18
Minimal DFA
Given following NFA find the minimal equivalent DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

88
views
theoryofcomputation
minimalstateautomata
numberofstates
finiteautomata
0
votes
1
answer
19
Conversion of NFA to DFA
convert the following NFA to DFA
asked
Dec 14, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

40
views
theoryofcomputation
finiteautomata
nfa
+2
votes
1
answer
20
Regular language
L={a^m b^n  mn=even} Is this language a regular language?
asked
Dec 12, 2018
in
Theory of Computation
by
AIkiran01
(
209
points)

176
views
theoryofcomputation
finiteautomata
regularlanguages
regularexpressions
identifyclasslanguage
0
votes
0
answers
21
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
(
2.2k
points)

63
views
theoryofcomputation
finiteautomata
#dfa
minimalstateautomata
0
votes
0
answers
22
proving a language is regular based on two regular language over same $\Sigma$ (complicated)
asked
Dec 9, 2018
in
Theory of Computation
by
csenoob
(
21
points)

28
views
regularlanguages
theoryofcomputation
finiteautomata
closureproperty
0
votes
0
answers
23
finding equivalence classes $R_L$ of given languages and separating words
hello, i've just solved 2 questions among many, but i'm not sure i've got to the right result. could you check if i did it correctly(especially 2) as it's more complicated). both are over ... classes. could you help me with that please? thank you very much for your help, really hoping i did it correctly.
asked
Dec 7, 2018
in
Theory of Computation
by
csenoob
(
21
points)

36
views
finiteautomata
equivalenceclasses
myhillnerode
theoryofcomputation
0
votes
0
answers
24
Extended transition function doubt
α (q1,aba) is {q0, q2} null reachable states are {q0, q1, q2} α (q3,bab) is {q0, q1, q2, q3} none what is extended transition function? and how to solve this kind of question?
asked
Dec 6, 2018
in
Theory of Computation
by
aditi19
Active
(
2.2k
points)

38
views
theoryofcomputation
finiteautomata
nfa
0
votes
0
answers
25
going from equivalnce classes into a DFA
Hello all, I saw an interesting question and i was wondering how to solve it. basically the subject i am having trouble with is going from equivalence classes of $R_L$ to building a DFA. The question: L is a language over {0,1}, for which ... how do you go from equivalence classes to finding the DFA? don't understand it. thank you very much for your help
asked
Dec 5, 2018
in
Theory of Computation
by
csenoob
(
21
points)

80
views
#dfa
finiteautomata
theoryofcomputation
compilerdesign
regularlanguages
0
votes
0
answers
26
Self doubt about relation between regular and linear grammar
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
asked
Nov 30, 2018
in
Theory of Computation
by
Abbas Ahmad
(
55
points)

25
views
theoryofcomputation
regulargrammar
finiteautomata
0
votes
0
answers
27
Condition for regular language to be infinite
Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove: The language L(M) is infinite iff it contains a string with length t, where n ≤ t < 2n. Please provide a prove. I am not getting it from the resources available on the ... we can accept infinite no. of strings isn't it? Then why doesn't this condition suffice? Please point out where I am going wrong.
asked
Nov 30, 2018
in
Theory of Computation
by
MiNiPanda
Boss
(
19.7k
points)

87
views
theoryofcomputation
finiteautomata
regularlanguages
0
votes
0
answers
28
formal language and automata by peter linz chapter 1.2 exercise 7
asked
Nov 22, 2018
in
Theory of Computation
by
Ashish RajAnand
(
13
points)

34
views
finiteautomata
0
votes
1
answer
29
DFA NFA
Given an NFA that recognizes L, to build an NFA to recognize the reverse of L , containing every string in reverse, it suffices to swap the initial and final states and reverse all edges. False. it is also false for DFA too.becz dfa may have more than one final state which will be changed to initial state after transformation i.e many initial state which is not possible. Am i correct?
asked
Nov 21, 2018
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
3.5k
points)

33
views
theoryofcomputation
finiteautomata
0
votes
1
answer
30
GATEECE2017
answer is D but I'm getting A. pls tell where am I going wrong?
asked
Nov 20, 2018
in
Digital Logic
by
aditi19
Active
(
2.2k
points)

75
views
digitallogic
sequentialcircuit
flipflop
digitalcounter
finiteautomata
Page:
1
2
3
4
5
6
...
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
Decidability Slides
How to Revise?
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
Follow @csegate
Gatecse
Recent questions tagged finiteautomata
Recent Blog Comments
https://gateoverflow.in/exam/136/appliedcourse20...
1 fulllength test and revision...
Good job Saurabh!
46,769
questions
51,221
answers
176,475
comments
66,581
users