Question

Today I learned about an abstract class of machines called linear bounded automata.

It is intended to model real-world computers that have a limited amount of memory. I have always thought that real computers are DFAs due to the finite memory (but the DFA is a terribly poor abstraction).

Is it possible to convert LBA into an equivalent DFA by making every possible tape configuration into a state of the DFA?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top