Theory of Computation

CHAPTER 3

A SUBSET OF THE URM LANGUAGE; FA AND NFA

This chapter is presented for enhanced completeness of coverage, but is a mostly “how to” chapter, rather than one that poses and answers fundamental questions on the limitations of computing,¹¹⁰ the latter being our central theme in this volume. Nevertheless, concepts and tools developed here are usable in the theory and practice of compiler writing, a principal area of application.

We will first introduce informally a modified and restricted URM. This new URM model will have explicit “read” instructions.¹¹¹

Secondly, any specific URM under this model will only have one variable that we may call generically “x”. This variable will always be of type digit; it cannot hold arbitrary integers, rather it can only hold digits as values. It has no stop instruction, nor instructions for adding/subtracting.

Pause. In the absence of a stop instruction, how does a computation halt? We postulate that our modified URMs halt simply by reading something unexpected, that is, an object that is not a member of the input alphabet of permissible digits. Such an illegal symbol serves as an end-marker of the useful stream digitss that constitute the input string over the given alphabet. As such it is often called an “end-of-file” marker, for short, eof.

Thus the modified URM halts if it runs out of input.

We next modify the permissible instructions ...