782
Modeling Arithmetic, Computation, and Languages
26. Find a Turing machine to compute the function
f (n 1 , n 2 ) = max(n 1 , n 2 )
27. Do Exercise 21 again, this time making use of the machines T 1 and T 2 of Exercises 16 and 23, respectively, as “functions.” (Formally, the states of these machines would have to be renumbered as the quintuples
are inserted into the “main program,” but you may omit this tiresome detail and merely “invoke T 1 ” or
“invoke T 2 .”)
28. Describe verbally the actions of a Turing machine that computes the function f (n 1 , n 2 ) = n 1 # n 2 , that
is, design the algorithm but do not bother to create all the necessary quintuples. You may make use of
Exercises 16 and 23.
S e c t i o n 9 . 5 ForMAl l AnguAgeS
Suppose we come upon the English language sentence, “The walrus talks loudly.”
Although we might be surprised at the meaning, or semantics, of the sentence,
we accept its form, or syntax, as valid in the language, meaning that the various
parts of speech (noun, verb, and so on) are strung together in a reasonable way. In
contrast, we reject, “Loudly walrus the talks,” as an illegal combination of parts
of speech, or as syntactically incorrect and not part of the language. We must
also worry about correct syntax in programming languages, but in these, unlike
natural languages (English, French, and so on), legal combinations of symbols are
specified in detail. Let’s give a formal definition of language; the definition will
be general enough to include both natural languages and programming languages.
DefinitionS ALPhABEt, voCABuLAry, worD, LAnGuAGE
An alphabet or vocabulary V is a finite, nonempty set of symbols. A word over
V is a finite-length string of symbols from V. The set V * is the set of all words
over V. (See Example 6 in Chapter 3 for a recursive definition of V*.) A language
over V is any subset of V *.
Viewing syntactically correct English language as a subset L of the set of all
strings over the usual alphabet, we feel that, “The walrus talks loudly,” belongs to
L while, “Loudly walrus the talks,” does not.
For any given language L, how can we describe L, that is, specify exactly
those words belonging to L? If L is finite, we can just list its members, but if L is
infinite, can we find a finite description of L? Not always—there are many more
languages than possible finite descriptions. Although we will consider only languages that can be finitely described, we can still think of two possibilities. We
may be able to describe an algorithm to decide membership in L; that is, given
any word in V*, we could apply our algorithm and receive a yes or no answer as
to whether the word belongs to L. Or we may be able to describe a procedure allowing us only to generate members of L, that is, crank out one at a time a list of
all the members of L. We will settle for languages for which this second option is
possible and describe such a language by defining its generative process, or giving
a grammar for the language.
Modeling Arithmetic, Computation, and Languages
26. Find a Turing machine to compute the function
f (n 1 , n 2 ) = max(n 1 , n 2 )
27. Do Exercise 21 again, this time making use of the machines T 1 and T 2 of Exercises 16 and 23, respectively, as “functions.” (Formally, the states of these machines would have to be renumbered as the quintuples
are inserted into the “main program,” but you may omit this tiresome detail and merely “invoke T 1 ” or
“invoke T 2 .”)
28. Describe verbally the actions of a Turing machine that computes the function f (n 1 , n 2 ) = n 1 # n 2 , that
is, design the algorithm but do not bother to create all the necessary quintuples. You may make use of
Exercises 16 and 23.
S e c t i o n 9 . 5 ForMAl l AnguAgeS
Suppose we come upon the English language sentence, “The walrus talks loudly.”
Although we might be surprised at the meaning, or semantics, of the sentence,
we accept its form, or syntax, as valid in the language, meaning that the various
parts of speech (noun, verb, and so on) are strung together in a reasonable way. In
contrast, we reject, “Loudly walrus the talks,” as an illegal combination of parts
of speech, or as syntactically incorrect and not part of the language. We must
also worry about correct syntax in programming languages, but in these, unlike
natural languages (English, French, and so on), legal combinations of symbols are
specified in detail. Let’s give a formal definition of language; the definition will
be general enough to include both natural languages and programming languages.
DefinitionS ALPhABEt, voCABuLAry, worD, LAnGuAGE
An alphabet or vocabulary V is a finite, nonempty set of symbols. A word over
V is a finite-length string of symbols from V. The set V * is the set of all words
over V. (See Example 6 in Chapter 3 for a recursive definition of V*.) A language
over V is any subset of V *.
Viewing syntactically correct English language as a subset L of the set of all
strings over the usual alphabet, we feel that, “The walrus talks loudly,” belongs to
L while, “Loudly walrus the talks,” does not.
For any given language L, how can we describe L, that is, specify exactly
those words belonging to L? If L is finite, we can just list its members, but if L is
infinite, can we find a finite description of L? Not always—there are many more
languages than possible finite descriptions. Although we will consider only languages that can be finitely described, we can still think of two possibilities. We
may be able to describe an algorithm to decide membership in L; that is, given
any word in V*, we could apply our algorithm and receive a yes or no answer as
to whether the word belongs to L. Or we may be able to describe a procedure allowing us only to generate members of L, that is, crank out one at a time a list of
all the members of L. We will settle for languages for which this second option is
possible and describe such a language by defining its generative process, or giving
a grammar for the language.