GATE CSE 1991 | Question: 17,a

Question

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.

Comments

@MiNiPanda AFAIK I think work tape is a memory just like we have stack as memory in PDA. But here work tape is bounded unlike stack memory which is unbounded. That's why I said this TM can't simulate PDA but it can simulate FA as no memory is required for FA.

---

So, u mean TM doesnot require memory?

---

Never said TM doesn't require memory. But this TM defined in the Q is limited in memory as it is mentioned "constant size work tape". To simulate FA this TM only needs read only input tape but it can't simulate PDA as work tape is limited in memory. Is this correct @Arjun Sir?

Answer 1

Regular languages can be finite or infinite.

Therefore , a finite tape turing machine can recognize all finite regular languages ..... here these set of finite regular languages can be called as a class of Regular languages.

Comments

nopes. We cannot say that. The question asks us to show that with a constant size work tape and no write capability, a TM must accept any regular language and not accept any non-regular language.

---

@Arjun sir, plz comment if i mistake.
Every such TM (TM1) moves looks like this-
$\delta(q,a)=(q',a,R)$  Or
$\delta(q,a)=(q',a,L)$

And every 2 DFA moves are also like this. We can have one to one correspondence between every 2DFA moves and this TM moves. i.e For every this type TM move, i can have a move for 2 DFA.

Tell me any move of this TM that cant be simulated in 2 DFA !

(that means, 2DFA$\supseteq$TM1. Now i need to prove that TM1$\supseteq$2DFA. Then only I can say 2DFA = TM1)
Constant size work tape means- Tape is restricted to input symbols only.
We dont need to go beyond input symbol to simulate 2-DFA.

Till now, I simulated this TM using 2DFA. and we can simulate other way round also.
Hence this TM is exactly equal to 2 DFA.
Hence it accepts precisely class of regular language.