Register

Materials:

Recent questions tagged decidability

1 1 vote
0 0 answers
182
182 views
This question was in a test series and I am bit confused with its solution , they have given option D as the solution .
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is un-decidable. Which of the following is TRUE?(A) P3 is decidable if P1 is reduc...
User Avatar
1 1 vote
0 0 answers
183
183 views
https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf
L = { ⟨ M ⟩ | M is a TM , M 0 is a TM that halts on all inputs , and M 0 ∈ L ( M ) } Is L even RE? The source says that there is a semi-decider(recognizer) TM such that i...
User Avatar
0 0 votes
2 2 answers
349
349 views
L = {<M> | <M> is a binary encoding of a TM which accepts some string of form ww^r } is L CFL ??
User Avatar
0 0 votes
1 1 answer
301
301 views
GO Classes Test Series 2025 | NIELIT Mock Test 1 | Question: 94
How many of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$$L^{\star}$ is infinite.$L$ is accepted by some DFA if and only if $L$ is...
User Avatar
16 16 votes
4 4 answers
7.1k
7.1k views
GATE CSE 2025 | Set 2 | Question: 15
​​​​Let $G_{1}, G_{2}$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$.Which ONE among...
User Avatar
Page: