2

You have a laptop with a fixed amount of memory and hard disk space and no external storage devices connected (CD, USB drives, . . . ). Which of the following is the most accurate formal model of your laptop?

(a) Turing machine (b) Linear bounded automaton (c) Pushdown automaton (d) Finite state automaton

First of all I don't mind saying that I could not interpret well enough. I understand it conveys that the memory is limited but how much that affect when it is connected to any external device is blur to me.Help appreciated.

N.B- This is not a homework question.Its from a pg admission exam.

Source- http://www.cmi.ac.in/admissions/sample-qp/pgcs2011.pdf

ViX28
  • 647
  • It just means that you can't increase the amount of storage by plugging in more USB drives etc. –  May 16 '16 at 17:28

1 Answers1

2

They just put the bit about external devices in so that you would be sure that you couldn't, for example, plug in a drive to make the storage bigger.

A Turing machine has an unlimited tape, so your finite-memory computer can't satisfy that. Similarly a pushdown automaton has a potentially-unlimited stack.

However, a computer is fully programmable, while a finite state machine is not. So, while strictly your computer has a finite number of states and well-defined transitions between them (since its memory and CPU together have only finitely many possible states), I would say it is more like a linear bounded automaton.

Patrick Stevens
  • 36,135