GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 30

Question

The language accepted by a Turing Machine if its Read/Write head is converted to a Read Only one is?

• A. Recursive but not necessarily context-free
• B. Deterministic context-free but not necessarily regular
• C. Regular
• D. None of the above

Answer 1

Without doing any writing to tape, the TM can only transition among the finite number of states. Its acceptance power reduces to that of a finite automata.

Reference: https://en.wikipedia.org/wiki/Two-way_finite_automaton

Comments

what about the tape length? if tape length is infinite still it will be FA ?

---

Who called it a finite automata? We only said the language accepted will be regular. It means the machine cannot accept any non regular language.

---

if language is regular it must have FA right ?

---

@Abhisheksmile94

FA accepts only a Regular language.

But a Regular language can be accepted by other machines also, like PDA, LBA, HTM, TM.