Register

Recent questions tagged turing-machine

0 0 votes
1 1 answer
473
473 views
#TOC #PDA #CFL
Question:LetL = { a^i b^j / i != 2j+1 } where i,j >=1  (a) Is LLL a deterministic context-free language (DCFL)?(b) Justify your answer with reasoning.
User Avatar
2 2 votes
1 1 answer
409
409 views
TIFR CSE 2025 | Part B | Question: 4
Consider the following languages:$L_{1}$ is the set of languages recognised by a deterministic pushdown automaton.$L_{2}$ is the set of languages recognised by a nondeter...
User Avatar
2 2 votes
1 1 answer
362
362 views
TIFR CSE 2025 | Part B | Question: 6
The complexity class $\textsf{NP}$ corresponds to the class of languages which can be accepted by some nondeterministic Turing machine in polynomial time.The complexity c...
User Avatar
0 0 votes
0 0 answers
354
354 views
Turing Machine Construction
how to make turing machine for 1^n0^n1^n
User Avatar
0 0 votes
0 0 answers
192
192 views
Create a transducer turing machine that computes this function
Create a transducer turing machine that computes this function:
User Avatar
1 1 vote
1 answers 1 answer
468
468 views
Decidability Marathon Part 2 - Theory of Computation | 200 Questions | Rice Theorem | Deepak Poonia
Please explain this statement, not able to get the intuition.
User Avatar
0 0 votes
1 1 answer
781
781 views
Made easy workbook
18. Which of the following is true?There are some regular languages for which no TM exists which accept itAll languages accepted by TM's are infiniteLanguages which are n...
User Avatar
0 0 votes
0 0 answers
444
444 views
TURING MACHINE UNDECIDABLITY
Whether a Turing machine accepts 2024 length string or not ?  
User Avatar
0 0 votes
0 0 answers
457
457 views
turing machine
Hello! can anyone please explain me this question. I am not getting the understanding what the verbose of this question is trying to tell us. PS : Please don't reject my ...
User Avatar
0 0 votes
0 0 answers
330
330 views
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
0 0 votes
0 0 answers
427
427 views
Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...
User Avatar
5 5 votes
1 1 answer
1.0k
1.0k views
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 64
Which of the following languages are Turing-recognizable?A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$.B. $\{\langle M\rangle...
User Avatar
1 1 vote
0 0 answers
900
900 views
Decidability
L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t understand why th...
User Avatar
0 0 votes
0 0 answers
748
748 views
Turing machine for a^n b^m c^n d^m NET UGC December 2022
The state diagram for the initial part of this turing machine given as:Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' ...
User Avatar
3 3 votes
2 2 answers
1.1k
1.1k views
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
User Avatar
0 0 votes
0 0 answers
450
450 views
UGC NET CSE | June 2023 | Part 2: 40
Given below are two statements:Statement I: If $f$ and $g$ are two functions and $f=O(g)$ but $g \neq o(f)$, we say that the growth rate of $g$ is smaller than that of $f...
User Avatar
1 1 vote
0 0 answers
404
404 views
UGC NET CSE | June 2023 | Part 2: 74
The set of turning machine codes for $\text{TM's}$ that accept all inputs that are palindromes (possible along with some other inputs) is decidableThe language of codes f...
User Avatar
0 0 votes
0 0 answers
476
476 views
UGC NET CSE | June 2023 | Part 2: 79
Consider following statements:I. A context free language is generated by $\text{LR(o)}$ grammar if and only if it is accepted by a deterministic pushdown automata and has...
User Avatar
0 0 votes
1 1 answer
555
555 views
UGCNET CSE December 2022: 29
The transition function ' $\delta$ ' in multi-tape Turing machine is defined as:$\delta: 2 \mathrm{Q} \times \Gamma^{\mathrm{k}} \rightarrow 2^{\mathrm{Q}} \times \Gamma^...
User Avatar
0 0 votes
0 0 answers
300
300 views
UGCNET CSE December 2022: 96
A Turing Machine for the language $\mathrm{L}=\left\{\mathrm{a}^{\mathrm{n}} \mathrm{b}^{\mathrm{m}} \mathrm{c}^{\mathrm{n}} \mathrm{d}^{\mathrm{m}} \mid \mathrm{n} \geq ...
User Avatar
Page: