Dark Mode

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

91 views

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

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

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

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

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

156 views

1 vote

1 answer

7

Igate Test Series
please explain all options with example

Amit Mehta asked in Theory of Computation Jul 20, 2022

283 views

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

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

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

414 views

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

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

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

809 views

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

706 views

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

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

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

Page:

1
2
3
4
5
6
...
15
next »

Recent questions tagged decidability