Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Materials:
Decidability Problems for Grammars
Some Reduction Inferences
Example reductions
Recent questions tagged decidability
1
votes
3
answers
421
English Terminology
Do we reduce PCP problem to our problem X to show that X is undecidable OR we reduce the problem X to PCP to show X's undecidability ?. A question has confused me in the terminology.
Do we reduce PCP problem to our problem X to show that X is undecidable OR we reduce the problem X to PCP to show X's undecidability ?. A question has confused me in the...
Mojo-Jojo
635
views
Mojo-Jojo
asked
Jan 3, 2016
Theory of Computation
theory-of-computation
decidability
+
–
1
votes
1
answer
422
MadeEasy Test Series: Theory of Computation- Decidabiliy
Let L be the language containing only the string S where S = 0 if you will never clear the gate. 1 if you will clear the gate some day. Which of the following is true? (L′ is the Complement of language L) L is decidable L′ is decidable L and L′ both are decidable L is undecidable
Let L be the language containing only the string S where S = 0 if you will never clear the gate. 1 if ...
Sandeep Singh
578
views
Sandeep Singh
asked
Dec 23, 2015
Theory of Computation
theory-of-computation
decidability
made-easy-test-series
+
–
2
votes
2
answers
423
Are the below two problems decidable ?
1. A turing machine prints a specific letter . 2.If L is CFL then L' is also CFL . For the second one ,it is known that L' will not be CFL but then why can't we design any algorithm for it ,since it is true that complement of CFL will never be true so then what is the essence here with respect to talking about decidable and undecidable ?
1. A turing machine prints a specific letter .2.If L is CFL then L' is also CFL .For the second one ,it is known that L' will not be CFL but then why can't we design any ...
radha gogia
1.3k
views
radha gogia
asked
Nov 20, 2015
Theory of Computation
decidability
+
–
2
votes
2
answers
424
How to remember decidability?
I want to know how to remember which language is decidable for which property. Should I go through the proofs or should I remember everything?
I want to know how to remember which language is decidable for which property. Should I go through the proofs or should I remember everything?
shikharV
2.2k
views
shikharV
asked
Nov 14, 2015
Theory of Computation
theory-of-computation
decidability
+
–
7
votes
2
answers
425
Decidability
$L = \{\langle M \rangle \mid M\text{ is a TM and } |L(M)| \leq 3\}$. Is it decidable or undecidable? Give the approach ?
$L = \{\langle M \rangle \mid M\text{ is a TM and } |L(M)| \leq 3\}$.Is it decidable or undecidable?Give the approach ?
Prashant.
2.1k
views
Prashant.
asked
Nov 13, 2015
Theory of Computation
decidability
+
–
1
votes
1
answer
426
Choose the decidable algorithm.
Please explain the decidablities of options A, C & D.
Please explain the decidablities of options A, C & D.
अनुराग पाण्डेय
356
views
अनुराग पाण्डेय
asked
Nov 5, 2015
Theory of Computation
decidability
+
–
21
votes
2
answers
427
TIFR CSE 2011 | Part B | Question: 25
Let $A_{TM}$ be defined as follows: $A_{TM}=\left \{ \left \langle M, w \right \rangle \mid \text{ The Turing machine $M$ accepts the word } w \right \}$ And let $L$ be some $\mathbf{NP}-$ complete language. Which of the following statements is ... Since $L$ is $\mathbf{NP}-$ complete, $A_{TM}$ is polynomial time reducible to $L$. $A_{TM} \notin \mathbf{NP}$.
Let $A_{TM}$ be defined as follows:$A_{TM}=\left \{ \left \langle M, w \right \rangle \mid \text{ The Turing machine $M$ accepts the word } w \right \}$And let $L$ be som...
makhdoom ghaya
2.1k
views
makhdoom ghaya
asked
Oct 20, 2015
Theory of Computation
tifr2011
theory-of-computation
decidability
+
–
1
votes
2
answers
428
IF L IS DECIDABLE THEN..
IF L IS DECIDABLE THEN 1)L&L' BE TURING RECOGNIZABLE 2)L MUST BE TURING RECOGNIZABLE BUT L' NEED NOT BE 3)EXACTLY ONE OF L AND L' BE TURING RECOGNIZABLE 4)L' IS TURING RECOGNIZABLE BUT L NEED NOT BE
IF L IS DECIDABLE THEN1)L&L' BE TURING RECOGNIZABLE2)L MUST BE TURING RECOGNIZABLE BUT L' NEED NOT BE3)EXACTLY ONE OF L AND L' BE TURING RECOGNIZABLE4)L' IS TURING RECOGN...
Himani Srivastava
1.8k
views
Himani Srivastava
asked
Oct 7, 2015
Theory of Computation
theory-of-computation
decidability
+
–
21
votes
3
answers
429
TIFR CSE 2010 | Part B | Question: 25
Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.) Given a CFG $G$, find whether $L(G) = R$, where $R$ is regular set. Given a CFG $G$, find whether $L(G) = \{\}$. Find whether ... whether CFG $G_1$ and CFG $G_2$ generate the same language, i.e, $L\left (G_1 \right ) = L\left (G_2 \right)$.
Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.)Given a CFG $G$, find whether $L(G) = R$, where $...
makhdoom ghaya
4.8k
views
makhdoom ghaya
asked
Oct 6, 2015
Theory of Computation
tifr2010
theory-of-computation
context-free-language
decidability
+
–
0
votes
2
answers
430
Consider $L_1$ and $L_2$, each over the alphabet $\Sigma$. Let $f: \Sigma \to \Sigma$ be
Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$. Let $f: \Sigma \to \Sigma$ ... $L_1$ is Undecidable and $L_2$ is Decidable (D) $L_1$ is Recursively Enumerable and $L_2$ is Recursive
Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$.Let $f: \Sigma \to \Sigma$ be a polynomial time, computable bijection, such that:$$\forall x: \le...
Pooja Palod
906
views
Pooja Palod
asked
Sep 19, 2015
Theory of Computation
decidability
theory-of-computation
+
–
5
votes
1
answer
431
Which of the following is not a recursive Language? Please explain the reason for each
Which of the following is not a recursive language? a. Regular language b. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$} c. {$\langle M \rangle$ | $M$ is a TM and there exists an input which halts within $100$ steps} d. {$\langle M \rangle$ | $M$ is a TM and $L(M)$ is regular }
Which of the following is not a recursive language?a. Regular languageb. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$}c. {$\langle M \rangle$ | $M$ is a TM and ...
Shefali
1.3k
views
Shefali
asked
Sep 11, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
+
–
2
votes
1
answer
432
S1: L ≤ m {0n1n | n ≥ 0} then L is decidable.
Answer True/False for the statements: S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable. S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable because enumerator for $L$ also enumerates $L’$.
Answer True/False for the statements:S1: $L ≤_m \{0^n1^n \mid n ≥ 0\}$ then $L$ is decidable.S2: if $L$ is R.E. and $L’ ⊆ L$ then $L’$ is recursively enumerable...
Anurag_s
2.0k
views
Anurag_s
asked
Aug 15, 2015
Theory of Computation
theory-of-computation
decidability
+
–
0
votes
1
answer
433
Relationship between Problems and Languages
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
Anurag_s
369
views
Anurag_s
asked
Aug 13, 2015
Theory of Computation
turing-machine
decidability
+
–
38
votes
4
answers
434
GATE CSE 2015 Set 3 | Question: 53
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to language $L_4$. Which of the following is/are true? $\text{ if } L_4 \in P, \text{ then } L_2 \in P$ ... $\text{ if } L_4 \in P, \text{ then } L_3 \in P$ II only III only I and IV only I only
Language $L_1$ is polynomial time reducible to language $L_2$. Language $L_3$ is polynomial time reducible to language $L_2$, which in turn polynomial time reducible to l...
go_editor
9.0k
views
go_editor
asked
Feb 16, 2015
Theory of Computation
gatecse-2015-set3
theory-of-computation
decidability
normal
+
–
48
votes
7
answers
435
GATE CSE 2015 Set 2 | Question: 21
Consider the following statements. The complement of every Turing decidable language is Turing decidable There exists some language which is in NP but is not Turing decidable If L is a language in NP, L is Turing decidable Which of the above statements is/are true? Only II Only III Only I and II Only I and III
Consider the following statements.The complement of every Turing decidable language is Turing decidableThere exists some language which is in NP but is not Turing decidab...
go_editor
15.3k
views
go_editor
asked
Feb 12, 2015
Theory of Computation
gatecse-2015-set2
theory-of-computation
decidability
easy
+
–
4
votes
2
answers
436
Whether given CFL is Regular is Decidable?
Which of the following are True? $S1$: Every NFA can be converted to equivalent PDA $S2$: Whether a given CFL is Regular is decidable. 1. $S1$ 2. $S2$ 3. Both 4. None
Which of the following are True?$S1$: Every NFA can be converted to equivalent PDA$S2$: Whether a given CFL is Regular is decidable.1. $S1$ ...
Vikrant Singh
3.8k
views
Vikrant Singh
asked
Jan 18, 2015
Theory of Computation
theory-of-computation
context-free-language
decidability
+
–
7
votes
2
answers
437
Given Language is REC or Non RE
Which of the following is true for the given language? $L=$ {<TM> | TM halts on every input} <TM> is encoding of the Turing machine (A) $L$ is Recursive and $\overline{L}$ is also Recursive (B) $L$ is Recursive ... Enumerable and $\overline{L}$ is Recursive Enumerable (D) $L$ is Non Recursive Enumerable and $\overline{L}$ is Non Recursive Enumerable
Which of the following is true for the given language?$L=$ {<TM | TM halts on every input}<TM is encoding of the Turing machine(A) $L$ is Recursive and $\overline{L}$ is ...
Manu Thakur
3.0k
views
Manu Thakur
asked
Nov 15, 2014
Theory of Computation
theory-of-computation
difficult
recursive-and-recursively-enumerable-languages
decidability
+
–
29
votes
2
answers
438
GATE CSE 1996 | Question: 1.9
Which of the following statements is false? The Halting Problem of Turing machines is undecidable Determining whether a context-free grammar is ambiguous is undecidable Given two arbitrary context-free grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$ Given two regular grammars $G_1$ and $G_2$ it is undecidable whether $L(G_1) = L(G_2)$
Which of the following statements is false?The Halting Problem of Turing machines is undecidableDetermining whether a context-free grammar is ambiguous is undecidableGive...
Kathleen
8.0k
views
Kathleen
asked
Oct 9, 2014
Theory of Computation
gate1996
theory-of-computation
decidability
easy
+
–
20
votes
2
answers
439
GATE CSE 1995 | Question: 11
Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below. $L$ is in NP and For every $n$, there is exactly one string of length $n$ that belongs to $L$. Let $L^c$ be the complement of $L$ over $\Sigma^*$. Show that $L^c$ is also in NP.
Let $L$ be a language over $\Sigma$ i.e., $L\subseteq \Sigma^*$. Suppose $L$ satisfies the two conditions given below.$L$ is in NP andFor every $n$, there is exactly one ...
Kathleen
3.6k
views
Kathleen
asked
Oct 8, 2014
Theory of Computation
gate1995
theory-of-computation
normal
decidability
proof
descriptive
+
–
34
votes
4
answers
440
GATE CSE 1997 | Question: 6.5
Which one of the following is not decidable? Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ steps Equivalence of two given Turing machines Language accepted by a given finite state machine is not empty Language generated by a context free grammar is non-empty
Which one of the following is not decidable?Given a Turing machine $M$, a string $s$ and an integer $k$, $M$ accepts $s$ within $k$ stepsEquivalence of two given Turing m...
Kathleen
10.0k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
decidability
easy
+
–
58
votes
2
answers
441
GATE CSE 2010 | Question: 17
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2 - L_1 \:\text{is recursively enumerable.}$ ... $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessar...
go_editor
16.0k
views
go_editor
asked
Sep 29, 2014
Theory of Computation
gatecse-2010
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
normal
+
–
32
votes
3
answers
442
GATE CSE 2014 Set 3 | Question: 35
Which one of the following problems is undecidable? Deciding if a given context-free grammar is ambiguous. Deciding if a given string is generated by a given context-free grammar. Deciding if the language generated by a given context-free grammar is empty. Deciding if the language generated by a given context-free grammar is finite.
Which one of the following problems is undecidable?Deciding if a given context-free grammar is ambiguous.Deciding if a given string is generated by a given context-free g...
go_editor
8.6k
views
go_editor
asked
Sep 28, 2014
Theory of Computation
gatecse-2014-set3
theory-of-computation
context-free-language
decidability
normal
+
–
43
votes
7
answers
443
GATE CSE 2012 | Question: 24
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$
Which of the following problems are decidable?Does a given program ever produce an output?If $L$ is a context-free language, then, is $\bar{L}$ also context-free?If $L$ i...
Arjun
15.5k
views
Arjun
asked
Sep 25, 2014
Theory of Computation
gatecse-2012
theory-of-computation
decidability
normal
+
–
44
votes
2
answers
444
GATE CSE 2013 | Question: 41
Which of the following is/are undecidable? $G$ is a CFG. Is $L(G) = \phi$? $G$ is a CFG. Is $L(G) = \Sigma^*$? $M$ is a Turing machine. Is $L(M)$ regular? $A$ is a DFA and $N$ is an NFA. Is $L(A) = L(N)$? $3$ only $3$ and $4$ only $1, 2$ and $3$ only $2$ and $3$ only
Which of the following is/are undecidable?$G$ is a CFG. Is $L(G) = \phi$?$G$ is a CFG. Is $L(G) = \Sigma^*$?$M$ is a Turing machine. Is $L(M)$ regular?$A$ is a DFA and $N...
Arjun
11.0k
views
Arjun
asked
Sep 24, 2014
Theory of Computation
gatecse-2013
theory-of-computation
decidability
normal
+
–
6
votes
1
answer
445
GATE CSE 1999 | Question: 10
Suppose we have a function HALTS which when applied to any arbitrary function $f$ and its arguments will say TRUE if function $f$ terminates for those arguments and FALSE otherwise. Example: Given the following function definition. FACTORIAL (N) ... have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.
Suppose we have a function HALTS which when applied to any arbitrary function $f$ and its arguments will say TRUE if function $f$ terminates for those arguments and FALSE...
Kathleen
1.6k
views
Kathleen
asked
Sep 23, 2014
Theory of Computation
gate1999
theory-of-computation
descriptive
decidability
+
–
52
votes
3
answers
446
GATE CSE 2005 | Question: 45
Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE? $P_3$ is decidable if $P_1$ is reducible to $P_3$ $P_3$ is undecidable if $P_3$ is reducible ... $P_3$ is undecidable if $P_2$ is reducible to $P_3$ $P_3$ is decidable if $P_3$ is reducible to $P_2$'s complement
Consider three decision problems $P_1$, $P_2$ and $P_3$. It is known that $P_1$ is decidable and $P_2$ is undecidable. Which one of the following is TRUE?$P_3$ is decidab...
Kathleen
12.1k
views
Kathleen
asked
Sep 22, 2014
Theory of Computation
gatecse-2005
theory-of-computation
decidability
normal
reduction
+
–
25
votes
2
answers
447
GATE CSE 2007 | Question: 6
Which of the following problems is undecidable? Membership problem for CFGs Ambiguity problem for CFGs Finiteness problem for FSAs Equivalence problem for FSAs
Which of the following problems is undecidable?Membership problem for CFGsAmbiguity problem for CFGsFiniteness problem for FSAsEquivalence problem for FSAs
Kathleen
5.6k
views
Kathleen
asked
Sep 21, 2014
Theory of Computation
gatecse-2007
theory-of-computation
decidability
normal
+
–
24
votes
1
answer
448
GATE CSE 2002 | Question: 14
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs a}$ $1\}$ ... step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs...
Kathleen
3.1k
views
Kathleen
asked
Sep 15, 2014
Theory of Computation
gatecse-2002
theory-of-computation
decidability
normal
turing-machine
descriptive
difficult
+
–
32
votes
3
answers
449
GATE CSE 2001 | Question: 7
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
Let a decision problem $X$ be defined as follows:$X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$?You may assume th...
Kathleen
4.5k
views
Kathleen
asked
Sep 14, 2014
Theory of Computation
gatecse-2001
theory-of-computation
decidability
turing-machine
easy
descriptive
+
–
53
votes
1
answer
450
GATE CSE 2001 | Question: 2.7
Consider the following problem $X$. Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$? Which of the ... ? $X$ is decidable $X$ is undecidable but partially decidable $X$ is undecidable and not even partially decidable $X$ is not a decision problem
Consider the following problem $X$.Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of ...
Kathleen
13.4k
views
Kathleen
asked
Sep 14, 2014
Theory of Computation
gatecse-2001
theory-of-computation
decidability
normal
+
–
Page:
« prev
1
...
10
11
12
13
14
15
16
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register