Greenlaw / Hoover Fundamentals of the Theory of Computation: Principles and Practice

Principles and Practice
1. Auflage 1998
ISBN: 978-0-08-050710-1
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 354 Seiten

This innovative textbook presents the key foundational concepts for a one-semester undergraduate course in the theory of computation. It offers the most accessible and motivational course material available for undergraduate computer theory classes. Directed at undergraduates who may have difficulty understanding the relevance of the course to their future careers, the text helps make them more comfortable with the techniques required for the deeper study of computer science. The text motivates students by clarifying complex theory with many examples, exercises and detailed proofs.* This book is shorter and more accessible than the books now being used in core computer theory courses. * Theory of computing is a standard, required course in all computer science departments.

Dr. Raymond Greenlaw is the Founder and Dean of the School of Computing and Professor of Computer Science at Armstrong Atlantic State University in Savannah, Georgia. Ray is theDistinguished Professor of Computer Science at Chiang Mai University in Thailand and a Distinguished Visiting Professor at the College of Management and Technology in Kuala Lumpur, Malaysia. He is the author of 13 books in the field of computer science. His books cover complexity theory, graph theory, the Internet, networking, operating systems, parallelcomputing, the theory of computation, and the World Wide Web. Dr. Greenlaw has published 60 research papers and given over 155 invited lectures throughout the world. As a PI or co-PI,Ray has been awarded over $6,000,000 in grants and contracts, and his research has been supported by the following countries: Germany, Hong Kong, Iceland, Italy, Japan, Malaysia, Spain, Taiwan, Thailand, and the United States. He has won numerous international awardsincluding three Senior Fulbright Fellowships, a Humboldt Fellowship, a Japanese Society forPromotion of Science Fellowship, two visiting Professor Fellowships from Italy, a SasakawaFellowship for Japanese Studios, and a Spanish Fellowship for Science and Technology. Dr. Greenlaw served as the Regional Coordinator for the State of Georgia's $100,000,000 Yamacraw Project, which was designed to make the state of Georgia a leader in thetelecommunications field. Ray serves as a Commissioner for the Computing AccreditationCommission (CAC) of the Accreditation Board for Engineering Technology (ABET). He received a Bachelor of Arts in Mathematics from Pomona College in 1983, a Master ofScience in Computer Science from the University of Washington in 1986, and a Ph.D. in Computer Science from the University of Washington in 1988.

Autoren/Hrsg.

Greenlaw, Raymond

Hoover, H. James

Leseproben

CHAPTER 2

Languages and Problems

 The computer says it’s a binary code.

 It’s just a pity I can’t understand it.

 —

2.1 Introduction

The purpose of computation is to solve problems. However, before we can attempt to solve a problem, we must communicate it to another person, a computer, or just ourselves. We do this with a . In very general terms, a language is a system of signs used to communicate information between one or more parties. In this book the language we use to talk computation is a combination of English and mathematics. But what about the language computation? That is, what language do we use to communicate problems to, and get answers from, our computing machines? Answering this question is the goal of this chapter.

Even equipped with a fancy graphical user interface, a computer remains fundamentally a symbol manipulator. Unlike the natural languages of humans, each symbol is precise and unambiguous. A computer takes sequences of precisely defined symbols as inputs, manipulates them according to its program, and outputs sequences of similarly precise symbols. If a problem cannot be expressed symbolically in some language, then it cannot be studied using the tools of computation theory.

Thus the first step of understanding a problem is to design a language for communicating that problem to a machine. In this sense, a is the fundamental object of computability. Let’s begin with some informal discussion and examples of this abstract concept of language before proceeding with the technical details.

Consider the following very general “problem”: develop a graphical user interface for evaluating arithmetic expressions that has the same look and feel as a physical calculator. What exactly is the problem here? At a high level, the problem faced by the programmer is to actually build such an application. This kind of problem belongs to the realm of algorithm design and software engineering.

We use the term “problem” in a much narrower sense. The problem in the calculator case is to evaluate arithmetic expressions. The problem consists of many , where each instance provides an input (in some suitable language) that gives a specific arithmetic formula to be evaluated. The value of the formula, which is the solution of the instance, is then output (again in some suitable language).

For example, if we run a calculator program online, the input is generated by clicking on the calculator’s buttons, as shown in Figure 2.1. We could create a legal input by clicking on the 4, 0, 6, ÷, 5, 0, and =. The solution to the problem would then appear in the display as the sequence of symbols 8.12. Of course, not all sequences of input symbols are legitimate instances of the problem, and only certain combinations of mouse clicks should be allowed by the input language. For example, clicking × first and then = would probably cause the calculator to complain that the input was invalid. Exactly how the valid and invalid combinations can be concisely specified is an interesting topic in itself that we discuss in Chapter 7.

Figure 2.1 An online calculator program. The buttons represent inputs to the calculator. An input is triggered or sent to the calculator program by clicking on the = key. Using the Clr key resets the entire input.

Intuitively, we as experienced calculator users know what is allowed in the language of expression evaluation. Arithmetic combinations such as 37.4 + 12.8 + 100.78 are okay; expressions such as 73.2 + +1 are not. But to talk about this problem in an exact mathematical sense requires us to precisely describe this language. In general, we will describe a problem as a task to be performed on a specific input. Inputs will consist of sequences of symbols, and outputs will be produced as sequences of symbols. Thus the arithmetic expression evaluation problem is to take as input an arithmetic expression, and to output its value.

Now consider the “problem” of correctly addressing email. Suppose you are submitting a form on the World Wide Web and one field asks for your email address. Figure 2.2 provides a typical scenario, and we see one field is labeled “email address.” What type of inputs would be syntactically correct here? You would probably expect things like or to be legal. That is, a user’s name followed by an @ symbol and then a domain name with each subdomain separated by a “dot.” Note that just because an address is syntactically correct does not mean that it actually corresponds to a real person.

Figure 2.2 An example of a form on the World Wide Web. What types of inputs are allowed in each field? The set of all possible inputs for a given field represents a language.

The problem in this case is for the script that processes the Web screen to check the input for proper form. The script should verify that the email address entered has the correct layout; that is, it contains only one @, contains tokens separated by dots, and so on. We can think of all the possible inputs of the correct format as the language of properly formatted email addresses. The form processing script should only allow the user to submit a form if the data specified by the user in the email field is, in fact, in the language of valid email addresses. This ensures that the user has correctly filled out the form. If someone types an email address like “hello world”, a string that is not in the language representing email addresses, the program should recognize this as an invalid address and reply “Sorry, invalid email address format.” All field validation problems are essentially checking if the supplied input is a legitimate string in some language. So, for example, we have the language of email addresses, the language of signed integer numbers, the language of monetary dollar amounts, and so on.

It is important to note that there is something fundamentally different about the languages associated with the calculator and Web problems. In the calculator case, the problem was to actually evaluate the input expression, so the language of the arithmetic expression problem has to handle both input and output communication. In the Web form case, the language simply described all the legitimate inputs to the field. In this case, there is no output to communicate other than the binary value of YES or NO, depending on whether the input was in the language or not. We will be dealing with both kinds of problems: those that have both an input and an output language, and those that have only an input language. What is interesting is that from a theory-of-computation perspective, almost all problems can be expressed just in terms of language recognition.

The theory of computation deals with the essence of problems and abstracts away many of the details. The goal of computation theory is to take a real-life problem, with all of its ugly implementation details and ambiguous behavior, and distill the core aspects: Is the problem solvable? How much time does a given instance take? How much memory does it use? How do time and memory requirements grow as the size of the instance gets bigger?

The problem with real-life computing can be described as the following:

1. There are many types of computers.

2. The details involving specific machines and circumstances (such as instruction set, processor speed, programming language installed, and so on) get rather involved and vary widely.

So one of the main goals of computation theory is to define abstract machines that hide many of the details of reality, yet capture the important factors. Designing these simple abstract machines is the goal of Chapters 4 and 6. But first we must be able to express our problems using symbols that can be manipulated in a computation.

2.2 Symbols, Alphabets, and Strings

Since we use languages to communicate, we usually must give the language some meaning (its ). However, much of the manipulation of , and languages can be done without understanding their semantics. Such manipulation is the subject of this section.

The most primitive notion we have is that of a symbol. Symbols are the atoms of the world of languages. A symbol is any single object such as #,0, 1, , or . Any object can be considered to be a symbol—for example, the keywords begin, else, or while. Usually, we will use only the characters from a typical keyboard as symbols.

We need at least one symbol to communicate; we normally need more, but never more than a fixed number. An alphabet is any finite, nonempty set of symbols. Let’s consider a few sample alphabets.

Example 2.2.1 Alphabets

1. Binary alphabet: {0,1}

2. Lowercase English alphabet:

3. First five letters of the uppercase English alphabet: {}

4. Portion of a calculator: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ÷, =, -, +, ×,...