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

"Constant size work tape" is Not sufficient for regularity ??? Myhill Nerode equivlnce class ..

---

Since the input tape size is fixed, let it be k and ∑ represent the input symbols then there can be total of (|∑|⁰ + |∑|¹+|∑|²+...|∑|^k) strings possible.

|∑|ⁱ represents no. of strings having length=i that are possible using |∑| input symbols.

For eg. if ∑={a,b} so |∑|=2 , and if i=1 then only 2¹strings of length i=1 can be made i.e. {a,b}.

Since the language is finite hence regular. Can we say like this @Arjun Sir?

---

Input size being finite or infinite is not mentioned (by default should be infinite) but work size tape which is different from input size tape is finite, so we can't recognize CFLs because we can't simulate stack operations as memory is limited. So certainly this TM is less powerful than a normal PDA though this TM can simulate Finite Automata as no memory is required in FA.

---

@rfzahid

Can you please give me some insight on work tape..?

---

@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

A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language.

https://en.wikipedia.org/wiki/Read-only_Turing_machine

Comments

Source : Wikipedia 

A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language.

Answer 2

ans can be PDA or FINITE AUTOMETA

which contain fixed space(FA with 1 STACK) , and can only make read operation,and accepts all regular languages

Comments

Can you explain how can it be a PDA?

---

I think FA.......if we restrict LBA with tape size then it will become FA and if we away ink in TM then it will become FA.

Answer 3

according to the CHOMSKY HEIRARCHI ,every FINITE AUTOMATA is an TURING MACHINE

so, every  FINITE AUTOMATA   is an TM ,with finite length in TAPE, and with an ACCESSABILITY of read only.

FA,PDA,LBA all are TM

Answer 4

I think the logic should be as follows:

WHAT DOES A FINITE AUTOMATA DO?

It sees the input one by one and switches the states according to the input.

NOW HOW READ-ONLY TM equals FA and not even CFL?

Now the input tape can be just used to read the input and nothing else. And work tape can be used to simulate the FA rules and accept/reject the input.

Since the work tape is also constant size and not O(input size), therefore we cannot even copy the input to work tape.

With write capability off, we cannot even pop the inputs and hence CFLs are also not possible. But just provide tape with stack operations capability and then the TM will even recognize the CFLs.