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.
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
+1
vote
1
answer
1
which of the following are true
asked
20 hours
ago
in
Theory of Computation
by
shivanisrivarshini
Veteran
(
14.9k
points)

19
views
theoryofcomputation
0
votes
0
answers
2
#TOC Undecidability
In this lecture by Shai Simonson : https://youtu.be/77OG6ziPMu4 At 33:04 he mentions that "A = CFL that does not accept $\sum^*$ " is Undecidable. Also, we already know that "A' = CFL that accept $\sum ^*$ " is Undecidable as well. so if A and A' both are Recursively Enumerable sets, then wouldn't that make A a recursive set ?
asked
21 hours
ago
in
Theory of Computation
by
Abbas2131
Active
(
1.8k
points)

13
views
theoryofcomputation
decidability
contextfreelanguages
+1
vote
1
answer
3
Peter Linz
Please help in creating the DFA for (na (w)nb (w))mod 3>0
asked
5 days
ago
in
Theory of Computation
by
Manish Kumar 24
(
21
points)

60
views
theoryofcomputation
peterlinz
0
votes
1
answer
4
Regular Expressions
L1={anbm:n>=3,m<=4} Find complement of L1
asked
Feb 14
in
Theory of Computation
by
Ahsanul Hoque
(
67
points)

66
views
regularlanguages
theoryofcomputation
+10
votes
3
answers
5
GATE201852
Given a language $L$, define $L^i$ as follows: $$L^0 = \{ \varepsilon \}$$ $$L^i = L^{i1} \bullet L \text{ for all } I >0$$ The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____
asked
Feb 14
in
Theory of Computation
by
gatecse
Veteran
(
18k
points)

1.5k
views
gate2018
theoryofcomputation
numericalanswers
+5
votes
3
answers
6
GATE201836
Consider the following problems. $L(G)$ denotes the language generated by a grammar $G$. L(M) denotes the language accepted by a machine $M$. For an unrestricted grammar $G$ and a string $w$, whether $w \: \epsilon \: L(G)$ Given a ... ? Only I and II are undecidable Only II is undecidable Only II and IV are undecidable Only I, II and III are undecidable
asked
Feb 14
in
Theory of Computation
by
gatecse
Veteran
(
18k
points)

1.2k
views
gate2018
theoryofcomputation
decidability
easy
+11
votes
11
answers
7
GATE201835
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n =p \text{ ... { where } m, n, p, q \geq 0 \}$ Which of the above languages are contextfree? I and IV only I and II only II and III only II and IV only
asked
Feb 14
in
Theory of Computation
by
gatecse
Veteran
(
18k
points)

1.7k
views
gate2018
theoryofcomputation
identifyclasslanguage
contextfreelanguage
normal
+3
votes
4
answers
8
GATE20187
The set of all recursively enumerable languages is closed under complementation closed under intersection a subset of the set of all recursive languages an uncountable set
asked
Feb 14
in
Theory of Computation
by
gatecse
Veteran
(
18k
points)

921
views
gate2018
theoryofcomputation
closureproperty
easy
+4
votes
2
answers
9
GATE20186
Let $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$. Which one of the following is necessarily true? $k \geq 2^n$ $k \geq n$ $k \leq n^2$ $k \leq 2^n$
asked
Feb 14
in
Theory of Computation
by
gatecse
Veteran
(
18k
points)

888
views
gate2018
theoryofcomputation
minimalstateautomata
normal
0
votes
1
answer
10
TOC RBR test series FA
question seems to be easy. but could not understand the solution
asked
Feb 11
in
Theory of Computation
by
Moin Mukhtar
(
319
points)

76
views
theoryofcomputation
finiteautomata
testseries
0
votes
1
answer
11
Complement of CFL
How to prove that "complement of L = {WWR  W ∈ {a,b}*} is CFL" ?
asked
Feb 11
in
Theory of Computation
by
ankitgupta.1729
Active
(
1.6k
points)

63
views
contextfreelanguage
theoryofcomputation
0
votes
1
answer
12
Doubt
What is encoding in Finite State machine?
asked
Feb 10
in
Theory of Computation
by
Angkit
Loyal
(
3.2k
points)

24
views
theoryofcomputation
0
votes
1
answer
13
CMI2017B3
Let Σ = {a, b}. Given words u, v ∈ Σ* , we say that v extends u if v is of the form xuy for some x, y ∈ Σ* . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u. ... Σ* and reports Yes if some word in the language of A extends u and No if no word in the language of A extends u.
asked
Feb 5
in
Theory of Computation
by
Tesla!
Veteran
(
14.4k
points)

53
views
cmi2017
theoryofcomputation
0
votes
1
answer
14
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 ∈ Σ* and erases all occurrences ... Erease$_{ab}$(L):= { Erease$_{ab}$(w)  w$\in$ L} Show that Erase$_{ab}$(L$_{even}$) is a regular language.
asked
Feb 5
in
Theory of Computation
by
Tesla!
Veteran
(
14.4k
points)

53
views
cmi2017
theoryofcomputation
+1
vote
1
answer
15
CMI2017A10
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference? (a) If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A (b) If the best ... we don't know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
asked
Feb 5
in
Algorithms
by
Tesla!
Veteran
(
14.4k
points)

46
views
cmi2017
algorithms
theoryofcomputation
+3
votes
1
answer
16
CMI2017A01
The regular expression (a*+b)* is equivalent to which of the following regular expressions: (a) a*b* (b) (a*b+b)* (c) (a+b*)* (d) (a*b)*
asked
Feb 5
in
Theory of Computation
by
Tesla!
Veteran
(
14.4k
points)

178
views
theoryofcomputation
regularexpressions
cmi2017
0
votes
0
answers
17
Regular Language
asked
Feb 2
in
Theory of Computation
by
vijay_jr
Active
(
1.2k
points)

46
views
theoryofcomputation
regularlanguages
finiteautomata
0
votes
1
answer
18
Grammer
Can I give any grammer for the language L = { anbncn / n>=1} Like this
asked
Feb 1
in
Theory of Computation
by
MRINMOY_HALDER
(
161
points)

43
views
theoryofcomputation
grammar
0
votes
1
answer
19
Regular expression
S > AaB A > aC  $\epsilon$ B > aB  bB  $\epsilon$ C > aCb  $\epsilon$ Is the regular expression for the above is this: a(a + b)* a ( a* + b* )* ?
asked
Feb 1
in
Theory of Computation
by
Tuhin Dutta
Boss
(
7.8k
points)

91
views
theoryofcomputation
regularexpressions
0
votes
0
answers
20
TOC ACE
asked
Feb 1
in
Theory of Computation
by
dm4006
Active
(
1.1k
points)

32
views
theoryofcomputation
0
votes
3
answers
21
Regular Expression
Can I write a* + b* = (a + b)* ????
asked
Jan 31
in
Theory of Computation
by
MRINMOY_HALDER
(
161
points)

85
views
regularexpressions
theoryofcomputation
identifiers
0
votes
0
answers
22
Test Series
We need to draw DFA for it. and then NFA.? Please tell the approach?
asked
Jan 31
in
Theory of Computation
by
Sahil1994
Active
(
1.3k
points)

31
views
theoryofcomputation
0
votes
0
answers
23
Type of Language
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
asked
Jan 31
in
Theory of Computation
by
Chhotu
Veteran
(
14.7k
points)

26
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
24
Minimal DFA
Minimum states if L is Language that accepts (a+b)* (aaa+aab) are ____ My ans : 4 states given ans : 5 states
asked
Jan 31
in
Theory of Computation
by
Anjan
Active
(
1.8k
points)

118
views
theoryofcomputation
minimalstateautomata
0
votes
0
answers
25
#Practise Class of Languages
$xwxw^r \ w,x \in (a,b)^*$ $wxw^{r}x \ w,x \in (a,b)^*$
asked
Jan 31
in
Theory of Computation
by
Anjan
Active
(
1.8k
points)

29
views
theoryofcomputation
regularlanguages
0
votes
0
answers
26
Turing Machine  Membership Problem
asked
Jan 31
in
Theory of Computation
by
Akash Mishra
Active
(
1.1k
points)

35
views
turingmachine
theoryofcomputation
+1
vote
1
answer
27
Theory of computation
The minimal finite automata accepting the set of all strings over 0,1 starting with 1 that interpreted as a binary representation of an integer are congruent to 0 modulo 5 has ___ states. What is this language?
asked
Jan 31
in
Theory of Computation
by
gauravkc
Loyal
(
4.1k
points)

36
views
theoryofcomputation
0
votes
0
answers
28
Regular Languages
Language {w  ww=www} is regular. How and what is this language?
asked
Jan 31
in
Theory of Computation
by
gauravkc
Loyal
(
4.1k
points)

23
views
theoryofcomputation
regularlanguages
0
votes
0
answers
29
#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 31
in
Theory of Computation
by
iarnav
Veteran
(
20k
points)

27
views
theoryofcomputation
finiteautomata
regularexpressions
regulargrammar
+1
vote
0
answers
30
Regular  Context Free?
Let L be a given contextfree language over the alphabet {a, b}. Construct L1, L2 as follows. Let L1 = L − {xyx  x, y ∈ {a, b}∗}, and L2 = L·L. Then, (A) Both L1 and L2 are regular. B) Both L1 and L2 are context free but not necessarily regular. (C) L1 is regular and L2 is context free. (D) L1 and L2 both may not be context free
asked
Jan 31
in
Theory of Computation
by
Tuhin Dutta
Boss
(
7.8k
points)

57
views
theoryofcomputation
contextfreelanguage
regularlanguages
Page:
1
2
3
4
5
6
...
73
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
isro sc 2017 2nd paper
Which college to expect?
Interview Guidance
CDAC CoursesAugust session
Counselling...
Follow @csegate
Gatecse
Recent questions tagged theoryofcomputation
Recent Blog Comments
Okay Thanks
i think they call everyone ith a score higher ...
@raviyogi Do you know what was the cutoff ot IIT ...
I think the exam has not yet been created.
Then why it's not appearing as a separate exam in ...
33,712
questions
40,255
answers
114,368
comments
38,885
users