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 theoryofcomputation
Webpage for Theory of Computation:
0
votes
0
answers
1
Peter Linz
Construct a DFA on {0, 1} where every 00 is followed immediately by 1
asked
20 hours
ago
in
Theory of Computation
by
aditi19
Active
(
2.3k
points)

35
views
theoryofcomputation
peterlinz
finiteautomata
regularlanguages
0
votes
1
answer
2
Made easy theory book
asked
3 days
ago
in
Theory of Computation
by
Jyoti Kumari97
(
225
points)

53
views
madeeasybooklet
theoryofcomputation
selfdoubt
0
votes
2
answers
3
Made easy theory book
Given answer is option c. Can anyone tell me how?
asked
4 days
ago
in
Theory of Computation
by
Jyoti Kumari97
(
225
points)

71
views
madeeasybooklet
selfdoubt
theoryofcomputation
regularexpressions
0
votes
1
answer
4
#ComplierDesign #DragonsBook
For any contextfree grammar there is a parser that takes at most O (n$^3$ ) time to parse a string of n terminals. True or False?
asked
Feb 9
in
Compiler Design
by
Reshu $ingh
(
329
points)

57
views
compilerdesign
theoryofcomputation
0
votes
0
answers
5
#PreviousYear #TOC #Compiler
Is the set of all syntactically valid C programs countable or uncountable? How can we prove so?
asked
Feb 9
in
Theory of Computation
by
Reshu $ingh
(
329
points)

51
views
theoryofcomputation
compiler
+2
votes
4
answers
6
GATE20197
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
384k
points)

1.7k
views
gate2019
theoryofcomputation
regularlanguages
+1
vote
3
answers
7
GATE201915
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
384k
points)

2.2k
views
gate2019
theoryofcomputation
pumpinglemma
0
votes
3
answers
8
GATE201931
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT contextfree? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
384k
points)

1.5k
views
gate2019
theoryofcomputation
contextfreelanguage
+3
votes
1
answer
9
GATE201934
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$ S2: Set of all syntactically valid C programs S3: Set of all languages over the alphabet $\{0,1\}$ S4; Set of all nonregular languages over the alphabet $\{ 0,1 \}$ Which of the above sets are uncountable? S1 and S2 S3 and S4 S2 and S3 S1 and S4
asked
Feb 7
in
Theory of Computation
by
Arjun
Veteran
(
384k
points)

1.7k
views
gate2019
theoryofcomputation
countableset
0
votes
2
answers
10
GATE201948
Let $Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identify 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
(
384k
points)

2.3k
views
gate2019
numericalanswers
theoryofcomputation
finiteautomata
0
votes
1
answer
11
#automata
Is intersction of two languages is also a language of the same type? RE AND REC which languages is decidable and un undecidable
asked
Jan 31
in
Theory of Computation
by
amit166
Junior
(
693
points)

28
views
theoryofcomputation
0
votes
1
answer
12
#TOC #Examples
Give examples of: Countable Infinite Set Countable Finite Set Uncountable Finite Set Uncountable Infinite Set
asked
Jan 31
in
Theory of Computation
by
Reshu $ingh
(
329
points)

53
views
theoryofcomputation
finiteautomata
regularexpressions
0
votes
0
answers
13
#TOC #PumpingLemma
What is Pumping length? Why we consider pumping length of certain numbers? Can Pumping length be 0?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
329
points)

40
views
theoryofcomputation
finiteautomata
0
votes
0
answers
14
#TOC #NesoAcademy #Tutorial
“ Every state on $\epsilon$ goes to itself in $\epsilon NFA$ “ How is this so?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
329
points)

34
views
theoryofcomputation
finiteautomata
0
votes
0
answers
15
#TOC #GeneralGuidance
I am new to the topic of TOC and finding it difficult to develop intuition for questions. Though,I am good with Mathematics and someone told TOC is mathematical concept. How should I study TOC specifically?
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
329
points)

33
views
theoryofcomputation
finiteautomata
regularexpressions
decidability
0
votes
0
answers
16
#TOC #DFANFA
How is Every DFA is NFA but not viceversa? Not able to get it. Please explain.
asked
Jan 30
in
Theory of Computation
by
Reshu $ingh
(
329
points)

21
views
theoryofcomputation
finiteautomata
0
votes
1
answer
17
#TOC #RegularLanguages
Are regular languages closed under intersection?
asked
Jan 29
in
Theory of Computation
by
Reshu $ingh
(
329
points)

42
views
theoryofcomputation
0
votes
1
answer
18
Madeeasytestseries Regular language
Consider the following language: L = {w w $\epsilon$ {0,1}* ; w has equal number of occurances of 001' and 010' } The solution they provided: The absolute difference between the number of occurrences of 001' and 010' is at most 1. Hence ... an occurrence of 010' (and viceversa)). But, since such info is not given, so how this can be a regular language?
asked
Jan 29
in
Theory of Computation
by
Harsh Kumar
Active
(
1k
points)

54
views
madeeasytestseries
theoryofcomputation
regularlanguages
0
votes
1
answer
19
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.3k
points)

66
views
theoryofcomputation
#dfa
0
votes
0
answers
20
Made easy test series advance toc regular expression reverse isomorphic
Consider the following regular expressions: I. 0(0+1)* II. 0* 10*1(0 +1)* III (0+10)*(1+€) IV.[(0*10* 10*)* +0*]10* A language L whose regular expression is r is said to be reverse isomorphic if L(r)= L(r^R). How many of the above regular expressions are reverse isomorphic?
asked
Jan 28
in
Theory of Computation
by
Ram Swaroop
Active
(
2.2k
points)

32
views
madeeasytestseries
theoryofcomputation
+1
vote
0
answers
21
Self curiosity
Can a grammar be both right recursive and ambiguous ? How?
asked
Jan 28
in
Compiler Design
by
Shashankesh Upadhyay
(
61
points)

47
views
compilerdesign
theoryofcomputation
0
votes
0
answers
22
Self doubt
Let say L1 is Dcfl and L2=~L1(~ is complement L=L1 Intersection L2 What is L??
asked
Jan 28
in
Theory of Computation
by
Aman Juyal
Junior
(
763
points)

41
views
theoryofcomputation
0
votes
0
answers
23
Self doubt
L={ <TM> L(TM)= not re} is it decidable or not if undecidable what specific set it belongs ?
asked
Jan 28
in
Theory of Computation
by
Aman Juyal
Junior
(
763
points)

34
views
theoryofcomputation
0
votes
0
answers
24
Consider a language L = {xaybzc ((a ≤ b) or (a > b)) and (a ≠ c)}. Select the correct option.
asked
Jan 28
in
Theory of Computation
by
AVICS
(
7
points)

44
views
theoryofcomputation
contextfreelanguage
0
votes
0
answers
25
made easy
let l,m,n be the 3 regular expressions. consider the following identities. 1.( l*m*n*)* = (lm*+mn*+nl*)* 2.(mn+m)*m = m(nm + m)* 3.(l*m*n*)* = (l* + m*n + n*)* 4.(l*m)* = (l+m)* how many of the above identities are correct?
asked
Jan 26
in
Theory of Computation
by
screddy1313
(
401
points)

68
views
theoryofcomputation
regularexpressions
0
votes
1
answer
26
#ReferenceBook #FutureProspect
Which reference book you guys use for Compiler Design? What are the research prospect in this domain?
asked
Jan 26
in
Compiler Design
by
Reshu $ingh
(
329
points)

40
views
compilerdesign
theoryofcomputation
0
votes
1
answer
27
self doubt
Consider the following Regular expression: (a+b)*abb(a+b)* (a+b)*a(a+b)*bb(a+b)* (a+b)*ab(a+b)*b(a+b)* (a+b)*abb(a+b)*a Which of the above regular expression are equivalent ?
asked
Jan 25
in
Theory of Computation
by
Raj Kumar 7
Active
(
1.3k
points)

49
views
theoryofcomputation
regularexpressions
0
votes
2
answers
28
#toc How to make DFA for this.
How to draw a DFA for the below language. $L$ = {$W  W \in$ $ (0, 1)^* $}; $W$ ends with 0 and contains the substring 100 } No. of states in minimal DFA.
asked
Jan 24
in
Theory of Computation
by
CSHuB
(
47
points)

62
views
theoryofcomputation
finiteautomata
0
votes
1
answer
29
Class of language
Please suggest me in briefly for revision . How to we test regular,dcfl,cfl,recursive and recursive enumeranle. Eg say if we can find the pattern it's regular. Please help
asked
Jan 24
in
Theory of Computation
by
Mayankprakash
Active
(
1.1k
points)

29
views
theoryofcomputation
identifyclasslanguage
0
votes
0
answers
30
ace test series question on Recursively Enumerable Language
asked
Jan 23
in
Theory of Computation
by
Shankar Kakde
(
369
points)

54
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
acetestseries
Page:
1
2
3
4
5
6
...
95
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
Official keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Relax... But....
Barc : Arjun Sir
JEST Sample Question
Follow @csegate
Recent questions tagged theoryofcomputation
Recent Blog Comments
Only one question that is "no.of NOR gates"...
Hey, I'm new here, but can you explain to me why...
How to challenge the key???
There was this graph coloring chromatic number...
47,904
questions
52,285
answers
182,217
comments
67,720
users