A deterministic single-tape Turing machine that leaves every scanned symbol unchanged and moves one cell right after every nonhalting transition. Such machines decide exactly the regular languages. A deterministic finite automaton simulates the finite control, with accepting states determined by the blank-only continuation after the input; conversely, a machine simulating a deterministic finite automaton halts on the first blank.

Ancestors (4)

  1. Turing machine
  2. Theoretical computer science
  3. Computer science
  4. Home

Incoming links (1)

Synonyms (1)

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version