Section 3.1 Recursive Definitions
163
PRaCtiCe 4 Show how to build the wff ((A ~ (B′)) S C) from the definition in Example 5.
■
■
PRaCtiCe 5 A recursive definition for the set of people who are ancestors of James could have the
following basis:
James’s parents are ancestors of James.
Give the inductive step.
Strings of symbols drawn from a finite “alphabet” set are objects that are
commonly encountered in computer science. Computers store data as binary
strings, strings from the alphabet consisting of 0s and 1s; compilers view program
statements as strings of tokens, such as key words and identifiers. The collection
of all finite-length strings of symbols from an alphabet, usually called strings over
an alphabet, can be defined recursively (see Example 6). Many sets of strings with
special properties also have recursive definitions.
example 6
The set of all (finite-length) strings of symbols over a finite alphabet A is denoted
by A*. The recursive definition of A* is
1. The empty string λ (the string with no symbols) belongs to A*.
2. Any single member of A belongs to A*.
3. If x and y are strings in A*, so is xy, the concatenation of strings x and y.
Parts 1 and 2 constitute the basis, and part 3 is the recursive step of this definition.
Note that for any string x, xλ = λx = x.
PRaCtiCe 6 If x = 1011 and y = 001, write the strings xy, yx, and yxλx.
■
■
PRaCtiCe 7 Give a recursive definition for the set of all binary strings that are palindromes, strings
that read the same forward and backward.
example 7
Suppose that in a certain programming language, identifiers can be alphanumeric
strings of arbitrary length but must begin with a letter. A recursive definition for the
set of such strings is
1. A single letter is an identifier.
2. If A is an identifier, so is the concatenation of A and any letter or digit.
A more symbolic notation for describing sets of strings that are recursively
defined is called Backus–Naur form, or BNF, originally developed to define the
163
PRaCtiCe 4 Show how to build the wff ((A ~ (B′)) S C) from the definition in Example 5.
■
■
PRaCtiCe 5 A recursive definition for the set of people who are ancestors of James could have the
following basis:
James’s parents are ancestors of James.
Give the inductive step.
Strings of symbols drawn from a finite “alphabet” set are objects that are
commonly encountered in computer science. Computers store data as binary
strings, strings from the alphabet consisting of 0s and 1s; compilers view program
statements as strings of tokens, such as key words and identifiers. The collection
of all finite-length strings of symbols from an alphabet, usually called strings over
an alphabet, can be defined recursively (see Example 6). Many sets of strings with
special properties also have recursive definitions.
example 6
The set of all (finite-length) strings of symbols over a finite alphabet A is denoted
by A*. The recursive definition of A* is
1. The empty string λ (the string with no symbols) belongs to A*.
2. Any single member of A belongs to A*.
3. If x and y are strings in A*, so is xy, the concatenation of strings x and y.
Parts 1 and 2 constitute the basis, and part 3 is the recursive step of this definition.
Note that for any string x, xλ = λx = x.
PRaCtiCe 6 If x = 1011 and y = 001, write the strings xy, yx, and yxλx.
■
■
PRaCtiCe 7 Give a recursive definition for the set of all binary strings that are palindromes, strings
that read the same forward and backward.
example 7
Suppose that in a certain programming language, identifiers can be alphanumeric
strings of arbitrary length but must begin with a letter. A recursive definition for the
set of such strings is
1. A single letter is an identifier.
2. If A is an identifier, so is the concatenation of A and any letter or digit.
A more symbolic notation for describing sets of strings that are recursively
defined is called Backus–Naur form, or BNF, originally developed to define the