This chapter introduces finite-state machines, a primitive, but useful computational model
for both hardware and certain types of software. We also discuss regular expressions, the
correspondence between non-deterministic and deterministic machines, and more on
grammars. Finally, we describe typical hardware components that are essentially physical
realizations of finite-state machines.