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
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged theoryofcomputation
Webpage for Theory of Computation:
+5
votes
4
answers
1
GATE2020CS7
Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s? $((0+1)^*1(0+1)^*1)^*10^*$ $(0^*10^*10^*)^*0^*1$ $10^*(0^*10^*10^*)^*$ $(0^*10^*10^*)^*10^*$
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

2k
views
gate2020cs
regularexpressions
normal
theoryofcomputation
+1
vote
4
answers
2
GATE2020CS8
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

981
views
gate2020cs
theoryofcomputation
+2
votes
3
answers
3
GATE2020CS10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic contextfree. $L$ is contextfree but not deterministic contextfree. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

1.2k
views
gate2020cs
theoryofcomputation
+5
votes
5
answers
4
GATE2020CS26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

1.1k
views
gate2020cs
theoryofcomputation
decidability
+2
votes
4
answers
5
GATE2020CS32
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ Which one of the following is TRUE? $L_1$ is ... $L_2$ is contextfree. Neither $L_1$ nor $L_2$ is context free. $L_1$ context free but $L_2$ is not contextfree.
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

1k
views
gate2020cs
theoryofcomputation
+3
votes
4
answers
6
GATE2020CS51
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________
asked
Feb 12
in
Theory of Computation
by
Arjun
Veteran
(
436k
points)

922
views
gate2020cs
numericalanswers
theoryofcomputation
+1
vote
2
answers
7
TIFR2020B2
Consider the following statements. The intersection of two contextfree languages is always contextfree The superset of a contextfree languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of all strings in which ... $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
asked
Feb 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

90
views
tifr2020
theoryofcomputation
contextfreelanguages
decidability
+2
votes
3
answers
8
ISRO202041
Minimum number of states required in DFA accepting binary strings not ending in $”101”$ is $3$ $4$ $5$ $6$
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.5k
points)

318
views
isro2020
theoryofcomputation
finiteautomata
normal
+1
vote
1
answer
9
ISRO202040
Which of the following classes of languages can validate an IPv4 address in dotted decimal format? It is to be ensured that the decimal values lie between $0$ and $255$. RE and higher CFG and higher CSG and higher Recursively enumerable language
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.5k
points)

265
views
isro2020
theoryofcomputation
normal
+1
vote
2
answers
10
ISRO202039
The language which is generated by the grammar $S \rightarrow aSabSbab$ over the alphabet of $\{a,b\}$ is the set of Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.5k
points)

165
views
isro2020
theoryofcomputation
contextfreegrammars
normal
+2
votes
2
answers
11
ISRO202038
Which of the following is true? Every subset of a regular set is regular Every finite subset of nonregular set is regular The union of two non regular set is not regular Infinite union of finite set is regular
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.5k
points)

169
views
isro2020
theoryofcomputation
regularlanguages
easy
+1
vote
3
answers
12
ISRO202037
Context free languages are closed under union, intersection union, kleene closure intersection, complement complement, kleene closure
asked
Jan 13
in
Theory of Computation
by
Satbir
Boss
(
25.5k
points)

171
views
isro2020
theoryofcomputation
contextfreelanguages
easy
+3
votes
0
answers
13
Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T$recognizable. Show that $MIN_{CFG}$ is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

103
views
michaelsipser
theoryofcomputation
contextfreegrammars
turingrecognizablelanguages
decidability
proof
+1
vote
0
answers
14
Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turingrecognizable. Show that $NECESSARY_{CFG} $is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

37
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
decidability
proof
0
votes
1
answer
15
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a singletape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

87
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

34
views
michaelsipser
theoryofcomputation
pushdownautomata
decidability
proof
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIXFREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefixfree}\}$.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

33
views
michaelsipser
theoryofcomputation
contextfreegrammars
turingmachine
decidability
proof
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

32
views
michaelsipser
theoryofcomputation
turingmachine
decidability
proof
+1
vote
0
answers
19
Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

31
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

15
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

31
views
michaelsipser
theoryofcomputation
turingmachine
decidability
ricetheorem
proof
0
votes
0
answers
22
Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A twodimensional finite automaton $(2DIMDFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

44
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
23
Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a twoheaded finite automaton $(2DFA)$ to be a deterministic finite automaton that has two readonly, bidirectional heads that start at the lefthand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.
asked
Oct 20, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

16
views
michaelsipser
theoryofcomputation
finiteautomata
turingmachine
decidability
proof
0
votes
0
answers
24
Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

22
views
michaelsipser
theoryofcomputation
turingmachine
decidability
reduction
proof
0
votes
0
answers
25
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turingrecognizable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

10
views
michaelsipser
theoryofcomputation
turingmachine
turingrecognizablelanguages
proof
0
votes
0
answers
26
Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

16
views
michaelsipser
theoryofcomputation
decidability
reduction
proof
0
votes
0
answers
27
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turingrecognizable iff $A \leq_{m} A_{TM}$.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

9
views
michaelsipser
theoryofcomputation
turingrecognizablelanguages
reduction
proof
0
votes
0
answers
28
Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

17
views
michaelsipser
theoryofcomputation
contextfreegrammars
reduction
postcorrespondenceproblem
decidability
proof
0
votes
0
answers
29
Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

12
views
michaelsipser
theoryofcomputation
decidability
proof
0
votes
0
answers
30
Michael Sipser Edition 3 Exercise 5 Question 19 (Page No. 240)
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.
asked
Oct 19, 2019
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
61.4k
points)

11
views
michaelsipser
theoryofcomputation
postcorrespondenceproblem
decidability
proof
Page:
1
2
3
4
5
6
...
131
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
Everything falls into place just work hard and trust the process
GATECSE 2020 Admissions Live Discussion
BARC Interview Experience 2019
IITGN PGDIIT Fees/Placement/other info.
Online Python Programming Course by IIT Kanpur
Follow @csegate
Recent questions tagged theoryofcomputation
Recent Blog Comments
Congrats bro. That was a massive jump from AIR...
Thank you all for the wishes :)
Which one to prefer Top...
Congratulation brother 🔥🔥🔥
Congo bro😊
51,925
questions
58,883
answers
200,235
comments
112,558
users