Register

Recent questions tagged turing-machine

0 0 votes
1 1 answer
1.1k
1.1k views
Doubt In Turing Machine syllabus, Peter Linz
I am confused, besides LBA! what should i do from these topics from this book?
User Avatar
0 0 votes
1 1 answer
775
775 views
turing machine
( All strings of even length over {a,b} Complement of (a+b)* (a+b)* All strings of odd length over {a,b}
User Avatar
0 0 votes
2 2 answers
3.3k
3.3k views
Turing machine and Recursive Language
If total turing machine is a proper subset of turing machine then why recursive language is not a proper subset of Recursive Enumerable ?
User Avatar
1 1 vote
0 0 answers
2.4k
2.4k views
MadeEasy Subject Test: Theory of Computation - Turing Machine
Hi Guys, I think $S_{1}$ is not TRUE because input could be copied in other part of tape. So power of TM will not reduce. What is your opinion ?
User Avatar
0 0 votes
0 0 answers
1.7k
1.7k views
Can epsilon be used as a tape alphabet in case of Turing Machine?
User Avatar
0 0 votes
0 0 answers
5.8k
5.8k views
Turing Machine
Draw a Turing machine for the following." Concatenate two strings w1 and w2 , where each string is generated over {a,b}"Can anyone tell me whether this solution is corre...
User Avatar
0 0 votes
1 1 answer
508
508 views
theory of computation 4
User Avatar
0 0 votes
1 1 answer
567
567 views
theory of computation 3
User Avatar
3 3 votes
1 1 answer
2.5k
2.5k views
Turing Machines
What is the smallest number of states can a TM have?
User Avatar
2 2 votes
0 0 answers
1.3k
1.3k views
does turing machine accept null?
does turing machine accept null? if not then those set of languages that are accepted by turing machine shoud not generate null string??
User Avatar
2 2 votes
0 0 answers
868
868 views
Turing Machine
Which of the following Strings are not generated by given TM.1) aabbaa2) Epsilon3) aabb
User Avatar
4 4 votes
1 answers 1 answer
1.7k
1.7k views
TOC CONCEPTUAL
Which are the correct arguments?1) if A is a subset of B, and B is decidable, than A is guaranteed to be decidable.2) If L is Turing-decidable and L' is regular. Then L ∩...
User Avatar
1 1 vote
1 1 answer
1.4k
1.4k views
#TOC Turing Machine Question
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine.I know, other way is correct i.e for every DTM there exi...
User Avatar
1 1 vote
2 answers 2 answers
3.1k
3.1k views
Decidability Question
a) language accepted by a CFG(Context free grammar) is nonempty.is it D or UD?
User Avatar
0 0 votes
1 1 answer
1.2k
1.2k views
Turing Machine Question
The set of turning machines which halt on empty input forms a recursively enumerable set?!True or False. Please also state your reason/explanation.AFAIK - TM accept Epsil...
User Avatar
3 3 votes
2 answers 2 answers
11.3k
11.3k views
Recursive Enumerable Language Doubt
We know, Recursive Enumerable Language is not closed under complement. a) So, let's say Y is a R.E language and recursive, then what would be Y' (Y complement)?b) Again Y...
User Avatar
2 2 votes
2 2 answers
1.5k
1.5k views
Some Questions on Decidabilty
1) Is it decidable whether a given Turing machine accepts any string at all? That is, is L(M) not equal to ∅? 2) Is it decidable whether a given Turing machine accepts a...
User Avatar
1 1 vote
0 0 answers
1.6k
1.6k views
Doubt regarding Turing Machine
I have read that T.M does not accept ε , but then in questions I have read T.M taking input ε ?Well, if T.M can't accept ε then why we are giving T.M the input ε ?Thank ...
User Avatar
4 4 votes
1 1 answer
3.3k
3.3k views
Turing Machine Decidability Question
L1= {⟨M⟩| M is a TM and |L(M)| = 5 }. we know about at least and at most case, but someone explain equal to case.Furthermore, I'll complie more questions in same thread o...
User Avatar
1 1 vote
0 0 answers
513
513 views
gatequestions
How to solve turing machine decidable/undecidable questions ? Do I need to mug them up ?
User Avatar
4 4 votes
1 1 answer
1.9k
1.9k views
TURING MACHINE
User Avatar
0 0 votes
3 3 answers
4.6k
4.6k views
2's complement addition of two negative numbers
Please give me an example of adding two negative numbers using 2's complement number system.Let's say:-7 + (-6)
User Avatar
2 2 votes
1 1 answer
2.1k
2.1k views
Decidability
1. {<M,w>| M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')}2. {<M>| M is a TM, and M is the only TM that ...
User Avatar
0 0 votes
1 answers 1 answer
808
808 views
Turing Machine
State True or False and why?1)Any language computable by TM must be Recursive2) If we replace the word "computable" with "accepted" does the question gives same meaning?
User Avatar
0 0 votes
0 0 answers
709
709 views
Turing Machine
Given transition table of TM as follows, 01Bq0qo,1,R,q0,0,Rq1,B,Rq1q0,1,Rq0,0,RHalt What is the language accepted by above single tape TM where q0 is start State.Tape ...
User Avatar
2 2 votes
1 answers 1 answer
3.4k
3.4k views
Decidable or undecidable
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?
User Avatar
3 3 votes
2 answers 2 answers
1.4k
1.4k views
theory of computation
$L=\{\langle M \rangle\mid M$ is a TM such that if $M$ accepts $w$ then $M$ accepts $ww$ also$\}$ Which of the following is correct? $L$ is decidable$L$ is recognizable ...
User Avatar
0 0 votes
1 1 answer
1.7k
1.7k views
Is this language accepted by a Turing Machine?
Is this language L accepted by a Turing Machine?L = a1n a2n a3n a4n .........amn || m,n 0Also, what about this language?L = a1n a2n a3n a4n .........ann || n 0
User Avatar
0 0 votes
1 answers 1 answer
572
572 views
How Finite automata is considered as Turing machine with a restricted tape length?
How Finite automata is considered as Turing machine with a restricted tape length?
User Avatar
Page: