We’re all used to having access to powerful computing devices with complex architectures and instruction sets, but fundamental ideas of computer science are based on far simpler devices. The basic idea is to begin with the simplest possible devices and determine what types of computations are possible. We’ll explore three such devices below, ranging from ones that can only perform simple operations like recognizing strings to ones that can carry out any algorithm.

Finite-State Automata

In this section, we’ll introduce an abstract machine—a computational model, not a physical machine—called a finite-state automaton (FSA) or ...

Get Racket Programming the Fun Way now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.