Recent questions tagged turing-machine

0 votes
1 answer
303
0 votes
1 answer
306
1 votes
0 answers
308
0 votes
1 answer
310
0 votes
0 answers
312
Set of all languages that are not Recursively Enumerable is uncountable.This is true. WHY?
0 votes
1 answer
315
Referring to the question https://gateoverflow.in/227957/self-doubtIf the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular langu...
2 votes
1 answer
316
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
2 votes
3 answers
319
1)Let G be CFG. Whether L(G) is CFL.Q)Is it decidable or not?2)Let G be CFG and unambiguous. Whether L(G) is CFL.Q)Is it decidable or not?
0 votes
0 answers
321
Construct a Turing Machine that computes length of a given input string. For Example, if the input is $abbaab$, the output should be $abbaab00110$.
0 votes
0 answers
322
Design a TM that accepts strings over the alphabet{a,b}i)Of even lengthii)containing the substring "abababa"iii)not containing two consecutive zeros
1 votes
0 answers
325
Construct a Turing Machine for the language of all strings of this form$L= \{(a^m)(b^n) \mid {\text{n is a multiple of m, and m belongs to N}\}}$
0 votes
1 answer
327
A turing machine $M$ halts if started with a blank tape. This is undecidable . Can somebody explain this in easiest way possible.
0 votes
1 answer
328
Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$.Can somebody explain the solution.
3 votes
2 answers
329
{$<M>\mid M$ is a $TM$ that doesn't accept any even number}what type of language is it?Recursively enumerableRecursiveNot recursively enumerablenone of the above