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 #dfa
+1
vote
1
answer
1
ACE ACADEMY: TOC
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ? (a) 4 (b) 16 (c) 20 (d) 24
asked
May 22
in
Theory of Computation
by
Hirak
Active
(
3.4k
points)

68
views
theoryofcomputation
numberofdfa
#dfa
0
votes
0
answers
2
Allen Carrer Institute: TOC1
How many no. of states in DFA for the following required expression? $(a + b + c) (a + b + c) (a + b + c) (a + b + c) ……… (n – 2)$ times $(a + b + c)^{+}$ $(1) $ $n – 1$ $(2) $ $n$ $(3) $ $n + 1$ $(4) $ $n + 2$ Plz confirm me the answer . Is it $(n1)$ or $n ?$
asked
Apr 11
in
Theory of Computation
by
srestha
Veteran
(
113k
points)

33
views
finiteautomata
#dfa
0
votes
0
answers
3
proving DFA stuck
This DFA fulfills: Define a function diff:{0,1}∗→Zdiff:{0,1}∗→Z, for w∈{0,1}∗w∈{0,1}∗, diff(w)=(diff(w)=(# of 1's in w)−(w)−(# of 0's in ww). Thus, diff(ϵ)=0diff(ϵ)=0; diff(0)=−1diff(0)=−1; diff(1)=1diff(1)=1. Let L={w∈{0,1}∗∣diff(w)=3m for ... the second option: ∀w∈{0,1}∗∀w∈{0,1}∗: a) if δ(q0,w)=q1δ(q0,w)=q1, then w∈L and w=0, for any a∈Z+a∈Z+. What would be the correct option?
asked
Apr 4
in
Other Colleges
by
iara84
(
5
points)

21
views
finiteautomata
theoryofcomputation
#dfa
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 2.3.7 Problem 2.3.6 (Page No. 67)
asked
Apr 3
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
44k
points)

17
views
ullman
theoryofcomputation
finiteautomata
#dfa
descriptive
0
votes
2
answers
5
self doubt
Let L = { (a^p)*  p is prime number } and input is {a} . what is minimum number of state in NFA and DFA ?
asked
Jan 28
in
Theory of Computation
by
Raj Kumar 7
Active
(
1.1k
points)

77
views
theoryofcomputation
#dfa
0
votes
0
answers
6
Geekforgeeks full length
Let L = (0+1)*1(0+1)^(n−1) and following statements regrading language L: The language L can be recognised by a nondeterministic automaton with (n+1) states. Deterministic automaton recognises this language must have at least 2^n states. (Assume n≥1). Which of the ...  According to me, L can be written as (0+1)*1(0+1)* which makes option D most suitable.
asked
Jan 22
in
Theory of Computation
by
vinay chauhan
Active
(
1.1k
points)

17
views
nfa
#dfa
theoryofcomputation
0
votes
1
answer
7
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
+1
vote
2
answers
8
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
(
4k
points)

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

152
views
finiteautomata
theoryofcomputation
#dfa
0
votes
1
answer
10
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
(
4k
points)

121
views
theoryofcomputation
finiteautomata
#dfa
minimalstateautomata
0
votes
0
answers
11
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
(
15
points)

91
views
#dfa
finiteautomata
theoryofcomputation
compilerdesign
regularlanguages
0
votes
1
answer
12
nielit scientists b
how many Dfa's exists with two states over input alphabet {0,1}? a) 16 b) 26 c) 32 d) 64
asked
Nov 22, 2018
in
Theory of Computation
by
shashank joshi
(
61
points)

55
views
theoryofcomputation
theoryofcomputation
#dfa
0
votes
0
answers
13
myself
what is the difference between union and cross product of dfa
asked
Nov 17, 2018
in
Theory of Computation
by
namvar
(
31
points)

17
views
#dfa
#theoryofcomputation
#union
#crossproduct
0
votes
0
answers
14
Can a^p where p is a prime number be an NFA?
Let l={ (ap )*  p is a prime number} and $\sum$={a}.The minimum number of states in NFA which can accept this language. This is a question from a test series,I just want to know if the question is valid as I feel raised to prime number will not be regular,correct me if I am wrong.Not asking for solution to the question but if the question is valid.
asked
Oct 16, 2018
in
Theory of Computation
by
sripo
Active
(
2.3k
points)

421
views
theoryofcomputation
finiteautomata
nfa
#dfa
regularlanguages
regularexpressions
0
votes
1
answer
15
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
16
ISI2017PCBB1(a)
Consider an alphabet $\Sigma = \{1, 2, 3\}$.Design a deterministic finitestate automaton (DFA) that accepts all strings in $\Sigma^*$ in which the digits appear in nondecreasing sequence, from left to right. For example, the string $1123$ and $222$ would be accepted, whereas $21333$ will not be accepted.
asked
Sep 20, 2018
in
Theory of Computation
by
jothee
Veteran
(
98.3k
points)

36
views
isi2017pcbb
theoryofcomputation
finiteautomata
#dfa
0
votes
3
answers
17
DoubtDFA
what is the grammar generated by the complement of this DFA and what is the type?
asked
Aug 29, 2018
in
Theory of Computation
by
aditi19
Active
(
4k
points)

46
views
finiteautomata
#dfa
+2
votes
2
answers
18
#Self Doubt
Minimum number of states in DFA over Ʃ = {0, 1} with each string contains odd number of 0’s or odd number of 1’s.
asked
Jul 30, 2018
in
Theory of Computation
by
himgta
Active
(
3.6k
points)

87
views
#dfa
0
votes
1
answer
19
#Self doubt
asked
Jul 30, 2018
in
Theory of Computation
by
himgta
Active
(
3.6k
points)

124
views
#dfa
0
votes
1
answer
20
minimum dfa
minimized dfa for strings starts with ab and ends with aba over Σ={a,b}
asked
Jul 23, 2018
in
Theory of Computation
by
Rahul_Rathod_
(
421
points)

92
views
theoryofcomputation
#dfa
0
votes
1
answer
21
peter linz
Let L be the language formed by L={anb  n>=0}. Find a DFA that accepts L2L.
asked
Jul 19, 2018
in
Theory of Computation
by
BASANT KUMAR
Active
(
2.6k
points)

55
views
#dfa
0
votes
1
answer
22
Made easy workbook
match the following Caption
asked
Jul 13, 2018
in
Theory of Computation
by
asharani97
(
81
points)

64
views
nfa
#dfa
0
votes
1
answer
23
CMI2017B1
Let $Σ = \{a, b, c\}$. Let Leven be the set of all even length strings in $Σ^*$ $(a)$ Construct a deterministic finite state automaton for $L_{even}$. $(b$) We consider an operation $Erase_{ab}$ that takes as input a string $w \in Σ^*$ and erases all occurrences of the ... $L:$ $Erase_{ab}(L)$:= $\{ Erase_{ab}(w)\ \ w\in L\}$ Show that $Erase_{ab}(L_{even}$) is a regular language.
asked
Feb 5, 2018
in
Theory of Computation
by
Tesla!
Boss
(
18k
points)

114
views
cmi2017
theoryofcomputation
finiteautomata
#dfa
0
votes
1
answer
24
mocktest
Which of the following regular expression generates the set of all strings not containing ‘baa’ as a substring over input alphabet {a, b}? (a) a*(b*a)* (b) a*b*ab (c) a*baba* (d) a*(ba+b)*
asked
Sep 10, 2017
in
Theory of Computation
by
gautam27
(
5
points)

91
views
#dfa
0
votes
0
answers
25
#peterlinz
I'm not getting where I'm wrong but the correct answer is first one . Kindly correct me plz Thanks :) sorry for the bad handwriting though Given below is the question...
asked
Sep 9, 2017
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.2k
points)

135
views
#dfa
finiteautomata
#nfa
#toc
+1
vote
2
answers
26
#peterlinz
Finding the regular expression step by step using state elimiination method
asked
Sep 9, 2017
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.2k
points)

102
views
#dfa
finiteautomata
0
votes
0
answers
27
Youtube Video
Y we don't include 00 in no of a's mod 3 is greater than or equal to no. of b's mod 2.
asked
Sep 5, 2017
in
Theory of Computation
by
Krishunker
(
5
points)

58
views
#toc
#theoryofcomputation
#dfa
+1
vote
1
answer
28
#peterlinz
I'm able to convert a NFA into DFA without this lambda transition , but not with this ... How do I convert it into DFA?
asked
Sep 4, 2017
in
Digital Logic
by
Pawan Kumar 2
Active
(
4.2k
points)

100
views
#dfa
#nfa
#toc
0
votes
0
answers
29
#peterlinz
Construct the DFA
asked
Sep 3, 2017
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.2k
points)

62
views
#dfa
finiteautomata
Page:
1
2
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 #dfa
Recent Blog Comments
Yes. Stock is over with Indiapost.
But on Amazon the stock is there and a way too...
Why no pay now option is showing , i wanted to...
49,807
questions
54,729
answers
189,338
comments
80,020
users