Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
0
votes
1
answer
1
#gate questions
which one true 1. Determining whether context-free grammar is un-decidable 2. Whether a given grammar is context-free is decidable
amit166
asked
in
Theory of Computation
Jan 29
by
amit166
91
views
decidability
1
vote
0
answers
2
DRDO CSE 2022 Paper 2 | Question: 12 (a)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cup L_{2}$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
62
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
1
vote
0
answers
3
DRDO CSE 2022 Paper 2 | Question: 13
Let $L$ be the following language. $L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$. Explain why the following Turing Machine description cannot decide the language $L$. ... $0,$ accept. Else, reject.
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
34
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
4-marks
1
vote
0
answers
4
DRDO CSE 2022 Paper 2 | Question: 12 (b)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L=\left\{a \circ b \mid a \in L_{1}, b \in L_{2}\right\}$ where $a$ o $b$ denotes the concatenation of the strings $a$ and $b$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
30
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
1
vote
0
answers
5
DRDO CSE 2022 Paper 2 | Question: 12 (c)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cap L_{2}$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
48
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
0
votes
2
answers
6
toc decidablity
M is a Turing Machine and M is the only Turing Machine that accepts L(M) is decidable. TRUE/FALSE
jugnu1337
asked
in
Theory of Computation
Nov 8, 2022
by
jugnu1337
156
views
theory-of-computation
decidability
true-false
1
vote
1
answer
7
Igate Test Series
please explain all options with example
Amit Mehta
asked
in
Theory of Computation
Jul 20, 2022
by
Amit Mehta
283
views
decidability
closure-property
0
votes
1
answer
8
MADE EASY 2022 Work book -Theory of Computation series
Let L be a regular language on alphabet Σ. The union of the myhill-nerode equivalence classes is always _____, and the pairwise intersection of the myhill-nerode equivalence classes is always Fill up the blanks
abhinowKatore
asked
in
Theory of Computation
Mar 7, 2022
by
abhinowKatore
161
views
theory-of-computation
regular-languages
finite-automata
minimal-state-automata
decidability
7
votes
2
answers
9
GATE CSE 2022 | Question: 36
Which of the following is/are undecidable? Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$ Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is ... $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.
Arjun
asked
in
Theory of Computation
Feb 15, 2022
by
Arjun
4.2k
views
gatecse-2022
theory-of-computation
turing-machine
decidability
multiple-selects
2-marks
2
votes
3
answers
10
Applied roots test series question.
Which of the following is/are undecidable? A = { M| M is TM that accepts exactly all the odd length strings} L = { M|M is a TM and L(M) is infinite} EQ = {<D,E> | D is a DFA , E is a regular expression and L(D) = L(E ... According the key option a' is also UNDECIDABLE why is that, where am I going wrong and is the idea I've thought for option b' correct?
srjsunny123
asked
in
Theory of Computation
Sep 6, 2021
by
srjsunny123
414
views
decidability
24
votes
1
answer
11
GATE CSE 2021 Set 2 | Question: 36
Consider the following two statements about regular languages: $S_1$: Every infinite regular language contains an undecidable language as a subset. $S_2$: Every finite language is regular. Which one of the following choices is correct? Only $S_1$ is true Only $S_2$ is true Both $S_1$ and $S_2$ are true Neither $S_1$ nor $S_2$ is true
Arjun
asked
in
Theory of Computation
Feb 18, 2021
by
Arjun
7.4k
views
gatecse-2021-set2
theory-of-computation
regular-language
decidability
2-marks
10
votes
5
answers
12
GATE CSE 2021 Set 1 | Question: 39
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable
Arjun
asked
in
Theory of Computation
Feb 18, 2021
by
Arjun
6.0k
views
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
3
votes
2
answers
13
UGC NET CSE | October 2020 | Part 2 | Question: 55
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems: Is $L(G_1)=L(G_2)$? Is $L(G_2) \leq L(G_1)$? Is $L(G_1)=R$? Which of the problems are undecidable? Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(a)$ and $(b)$ only $(a)$, $(b)$ and $(c)$
go_editor
asked
in
Theory of Computation
Nov 20, 2020
by
go_editor
809
views
ugcnetcse-oct2020-paper2
theory-of-computation
decidability
1
vote
1
answer
14
UGC NET CSE | October 2020 | Part 2 | Question: 87
Given below are two statements: Statement $I$: The problem Is $L_1 \wedge L_2 = \phi$? is undecidable for context sensitive languages $L_1$ and $L_2$ Statement $II$: The problem Is $W \in L$? is decidable for context ... are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
go_editor
asked
in
Theory of Computation
Nov 20, 2020
by
go_editor
706
views
ugcnetcse-oct2020-paper2
theory-of-computation
decidability
1
vote
2
answers
15
NIELIT 2017 DEC Scientist B - Section B: 11
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: ... to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
1.5k
views
nielit2017dec-scientistb
theory-of-computation
decidability
27
votes
7
answers
16
GATE CSE 2020 | Question: 26
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
Arjun
asked
in
Theory of Computation
Feb 12, 2020
by
Arjun
10.3k
views
gatecse-2020
theory-of-computation
decidability
2-marks
2
votes
4
answers
17
TIFR CSE 2020 | Part B | Question: 2
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free 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 ... Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
Lakshman Patel RJIT
asked
in
Theory of Computation
Feb 11, 2020
by
Lakshman Patel RJIT
1.2k
views
tifr2020
theory-of-computation
context-free-language
decidability
Page:
1
2
3
4
5
6
...
15
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
My journey from being a MSc student to AIR 239 in GATE CSE 2023 and qualified UGC-NET JRF.
NEEPCO Recruitment 2023
GATE CSE 2023 Results
IIIT Banglore MTech 2023-24
IIIT-Delhi MTech 2023-24
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(653)
Exam Queries
(844)
Tier 1 Placement Questions
(17)
Job Queries
(76)
Projects
(9)
Unknown Category
(866)
Recent questions tagged decidability
Recent Blog Comments
congrats pranab
Congratulations @Pranab Paul 10 🥳
sir give access to these tests at least mid May...
Was there interview for mtech as well?
Check CCMT website for previous year cutoff for...