1,352 views
2 votes
2 votes

If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine 

$A)$ Regular Language

$B)$ CFL

$C)$ CSL

$D)$ None


Ans given CSL 

but I thought it should be regular

then what is difference between input restricted and constant size tape?

https://gateoverflow.in/26653/gate1991-17-a

Plz confirm what is correct?

 

2 Answers

0 votes
0 votes
remember :

TM with fixed length tape is a FA and TM with the tape length limited to the input is LBA ( linear bound automata ) hence the answer is CSL.

edit : mistyped Linear bound automata as lower bound automata
edited by
0 votes
0 votes

Linear Bound Automata

A non-deterministic TM is called linear bound automata (LBA) if,

  • It's input alphabet includes two special symbols $\varnothing$ and $\$$ as left and right end markers.
  • It has no moves beyond thee end markers, i.e, no left move from $\varnothing$ and no right move from $\$$.
  • It never changes the symbols $\varnothing$ and $\$$.

LBA accepts CSL. Hence option is C.

Theorem: If L is a CSL, then L is accepted by some LBA.

 

Related questions

3 votes
3 votes
2 answers
2
3 votes
3 votes
1 answer
3
3 votes
3 votes
2 answers
4