Recent questions tagged turing-machine / GATE Overflow for GATE CSE

0 votes

0 answers

1

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

Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape

RahulVerma3

46 views

RahulVerma3 asked Apr 2

0 votes

0 answers

2

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 as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?

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...

dopq12

91 views

dopq12 asked Mar 5

5 votes

1 answer

3

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 \mid M$ is a nondeterministic Turing machine and $M$ accepts 010 ... $\left\{\langle M\rangle \mid M\right.$ is a Turing machine and $\left.L(M)=\Sigma^*\right\}$.

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...

GO Classes

501 views

GO Classes asked Feb 5

5 votes

1 answer

4

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.

Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$....

GO Classes

494 views

GO Classes asked Jan 28

4 votes

1 answer

5

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 64
Which of the following statements about Turing machines is false? For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of $L$. For any grammar $G$ ... Turing machine $A$ which can simulate the behaviour of any given Turing machine $B$ on any given finite input.

Which of the following statements about Turing machines is false?For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of...

GO Classes

538 views

GO Classes asked Jan 13

1 votes

0 answers

6

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 this is not decidable. We can easily create a turing that accepts this language

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 ...

amitarp818

238 views

amitarp818 asked Dec 28, 2023

0 votes

0 answers

7

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' to X2. After that we go back in ... it wrong by skipping one state and directly looping back to 'q0' Please shed some light on it, thanks!

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' ...

Picturesque

248 views

Picturesque asked Oct 31, 2023

3 votes

2 answers

8

TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?

Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?

Jiten008

361 views

Jiten008 asked Oct 24, 2023

0 votes

0 answers

9

Design Turing machines to compute the following functions for x and y positive integers represented in unary. (a) f(x) = 3x

sridharsiddi

786 views

sridharsiddi asked Apr 16, 2023

0 votes

0 answers

10

Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.

Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells f...

borhanElmi

317 views

borhanElmi asked Feb 8, 2023

1 votes

0 answers

11

DRDO CSE 2022 Paper 2 | Question: 12 (a)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cup L_{2}$

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...

admin

294 views

admin asked Dec 15, 2022

2 votes

0 answers

12

DRDO CSE 2022 Paper 2 | Question: 13
Let $L$ be the following language. $L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$. Explain why the following Turing Machine description cannot decide the language $L$. ... $0,$ accept. Else, reject.

Let $L$ be the following language.$L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$.Explain why the following ...

admin

244 views

admin asked Dec 15, 2022

1 votes

0 answers

13

DRDO CSE 2022 Paper 2 | Question: 12 (b)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L=\left\{a \circ b \mid a \in L_{1}, b \in L_{2}\right\}$ where $a$ o $b$ denotes the concatenation of the strings $a$ and $b$

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...

admin

191 views

admin asked Dec 15, 2022

1 votes

0 answers

14

DRDO CSE 2022 Paper 2 | Question: 12 (c)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cap L_{2}$

Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turi...

admin

268 views

admin asked Dec 15, 2022

3 votes

2 answers

15

Turing machine question
I saw question where I saw this format being used: L1 = {<M> | L(M) = ϕ} What does exactly <M> mean and why is L(M) = ϕ, mentioned afterwards. Isn’t L() stands for language for something? If the language is equivalent to null, it contains nothing. Then what does it exactly mean?

I saw question where I saw this format being used:L1 = {<M | L(M) = ϕ}What does exactly <M mean and why is L(M) = ϕ, mentioned afterwards. Isn’t L() stands for langua...

h4kr

724 views

h4kr asked Dec 7, 2022

4 votes

1 answer

16

GO Classes Test Series 2023 | Theory of Computation | Test 5 | Question: 4
Consider the following languages : $\mathrm{L} 1:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{L}(\mathrm{M})\}.$ ... and $|\text{M}|<1000\} .$ Which of the above languages is Decidable? Only $\text{L1}$ Only $\text{L2}$ Both None

Consider the following languages :$\mathrm{L} 1:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{L...

GO Classes

623 views

GO Classes asked Aug 1, 2022

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true