test
*
Construction Techniques
*
Section 3.1 Inductively Defined Sets
To define a set S inductively is to do three things:
Basis: Specify one or more elements of S.
Induction: Specify one or more rules to construct elements of S from existing elements of S.
Closure: Specify that no other elements are in S (always assumed).
Note: The basis elements and the induction rules are called constructors.
Example 1. Find an inductive definition for S = {3, 16, 29, 42, …}.
Solution: Basis: 3 S.
Induction: If x S then x + 13 S.
The constructors are 3 and the operation of adding 13. Also, without closure, many sets
would satisfy the basis and induction rule. e.g., 3 Z and x Z implies x + 13 Z.
Example 2. Find an inductive definition for S = {3, 4, 5, 8, 9, 12, 16, 17, 20, 24, 33,…}.
Solution: To simplify things we might try to “divide and conquer” by writing S as the union
of more familiar sets as follows:
S = {3, 5, 9, 17, 33, …} {4, 8, 12, 16, 20, 24, …}.
Basis: 3, 4 S.
Induction: If x S then (if x is odd then 2x – 1 S else x + 4 S).
Example 3. Describe the set S defined inductively as follows:
Basis: 2 S;
Induction: x S implies x 3 S.
Solution: S = {2, 5, 8, 11, … } {–1, –4, –7, –10, … }.
*
*
Example 4. Find an inductive definition for S = {L, ac, aacc, aaaccc, …} = {ancn | n N}.
Solution: Basis: L S.
Induction: If x S then axc S.
Example 5. Find an inductive definition for S = {an+1bcn | n N}.
Solution: Basis: ab S.
Induction: If x S then axc S.
Example 6. Describe the set S defined by: Basis: a, b S
Induction: x S implies ƒ(x) S.
Solution: S = {a, ƒ(a), ƒ(ƒ(a)), …} {b, ƒ(b), ƒ(ƒ(b)), …}, which could also be written as
S = {ƒn(a) | n N} {ƒn(b) | n N} = {ƒn(x) | x {a, b} and n N}.
Example 7. Describe the set S defined by: Basis: 0 S
Induction: x S implies cons(1, x) S.
Solution: S = { 0 , 1, 0 , 1, 1, 0 , …}.
Infix notation
cons(h, t) = h :: t. Associate to the right. e.g., x :: y :: z = x :: (y :: z).
Example 8. Find an inductive definition for S = { , a, b , a, b, a, b , …}.
Solution: Basis: S.
Induction: x S implies a :: b :: x S.
Example 9. Find an inductive definition for S = { , , , …}.
Solution: Basis: S.
Induction: x S implies x :: S.
*
*
Notation for Binary Trees
Let t(L, x, R) denote the tree with root x, left subtree L, and right subtree R. Let denote the
empty binary tree. If T = t(L, x, R), then root(T) = x, left(T) = L, and right(T) = R.
Example 10. Describe the set S defined inductively as follows:
Basis: t( , •, ) S.
Induction: T S implies t(T, •, t( , •, )) S.
Solution (picture): The first few trees constructed from the definition are pictured as follows:
Example 11. Find an inductive definition for the set S of binary trees indicated by the
following picture.
Solution: Basis: t( , •, ) S.
Induction: T S implies t(t(left(T), •, ), •, t( , •, right(T))) S.
and so on.
and so on.
*
*
Example 12. Find an inductive definition for the set S = {a}* N.
Solution: Basis: (, 0) S.
Induction: (s, n) S implies (as, n), (s, n + 1) S.
Example 13. Find an inductive definition for the set S = {(x, –y) | x, y N and x ≥ y}.
Solution: To get an idea about S we can write out a few tuples:
(0, 0), (1, 0), (1, –1), (2, 0), (2, –1), (2, –2), and so on.
Quiz (2 minutes). Try to find a solution that does not construct repeated elements.
Solution: We might use two separate rules. One rule to construct the diagonal points and one
rule to construct horizontal lines that start at the diagonal points.
Basis: (0, 0) S.
Induction: 1. (x, y) S implies (x + 1, y) S.
2. (x, –x) S implies (x + 1, – (x + 1)) S.
We can also get an idea about S by graphing a few points,
as indicated in the picture.
One solution can be written as follows:
Basis: (0, 0) S.
Induction: (x, y) S implies (x + 1, y), (x + 1, y – 1) S.
Notice that this definition constructs some repeated points.
For example, (2, –1) is constructed twice.
*
*
Section 3.2 Recursively Defined Functions and Procedures
A function ƒ is recursively defined if at least one value ƒ(x) is defined in terms of another
value ƒ(y), where x ≠ y. Similarly, a procedure P is recursively defined if the action of P(x)
is defined in terms of another action P(y), where x ≠ y.
Technique for recursive definitions when the argument domain is inductively defined.
1. Specify a value ƒ(x), or action P(x), for each basis element x of S.
2. Specify rules that, for each inductively defined element x in S, define the value ƒ(x), or
action P(x), in terms of previously defined values of ƒ, or actions of P.
Example 1. Find a recursive definition for the function ƒ : N N defined by
ƒ(n) = 0 + 3 + 6 + … + 3n.
Solution: Notice that N is an inductively defined set: 0 N; n N implies n + 1 N. So
we need to give ƒ(0) a value in N and we need to define ƒ(n + 1) in terms of ƒ(n). The given
definition of ƒ tells us to set ƒ(0) = 0. To discover a definition for ƒ(n + 1) we can write
ƒ(n + 1) = (0 + 3 + 6 + … + 3n) + 3(n + 1)
= ƒ(n) + 3(n + 1).
So we have a recursive definition for ƒ:
ƒ(0) = 0
ƒ(n + 1) = ƒ(n) + 3(n + 1).
Two alternative definitions:
- ƒ(0) = 0
ƒ(n) = ƒ(n – 1) + 3n (n > 0).
- (if-then-else form): ƒ(n) = if n = 0 then 0 else ƒ(n – 1) + 3n.
*
*
Example 2. Find a recursive definition for cat : A* A* A* defined by cat(s, t) = st.
Solution: Notice that A* is inductively defined: L A*; a A and x A* imply ax A*,
where ax denotes the string version of cons. We can define cat recursively using the first
argument. The definition of cat gives cat(L, t) = Lt = t. For the recursive part we can write
cat(ax, t) = axt = a(xt) = acat(x, t). So we have a definition:
cat(L, t) = t
cat(ax, t) = acat(x, t).
If-then-else form using head and tail for strings:
cat(s, t) = if s = L then t else head(s)cat(tail(s), t).
Example 3. Find a definition for ƒ : lists(Q) Q defined by ƒ(x1, …, xn) = x1 + … + xn.
Solution: The set lists(Q) is inductively defined:
lists(Q); h Q and t lists(Q) imply h :: t lists(Q).
To discover a recursive definition, we can use the definition of ƒ as follows:
ƒ(x1, …, xn) = x1 + … + xn
= x1 + (x2 + … + xn)
= x1 + ƒ(x2, …, xn)
= head(x1, …, xn) + ƒ(tail(x1, …, xn).
So if we let ƒ( ) = 0, we have a recursive definition:
ƒ( ) = 0
ƒ(h :: t) = h + ƒ(t).
If-then-else form: ƒ(L) = if L = then 0 else head(L) + ƒ(tail(L)).
*
*
Example 4. Given ƒ : N N defined recursively by
ƒ(0) = 0
ƒ(1) = 0
ƒ(x + 2) = 1 + ƒ(x).
The if-then-else form for ƒ can be written as follows:
ƒ(x) = if x = 0 or x = 1 then 0 else 1 + ƒ(x – 2).
What does ƒ do?
Answer: List a few values to get the idea. For example,
map(ƒ, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) = 0, 0, 1, 1, 2, 2, 3, 3, 4, 4.
So ƒ(x) returns the floor of x/2. i.e., ƒ(x) = x/2.
Example 5. Find a recursive definition for ƒ : lists(Q) Q defined by
ƒ(x1, …, xn) = x1x2 + x2x3 + … + xn–1xn.
Solution: Let ƒ( ) = 0 and ƒ(x) = 0. Then for n ≥ 2 we can write
ƒ(x1, …, xn) = x1x2 + (x2x3 + … + xn–1xn) = x1x2 + ƒ(x2, …, xn).
So we have the following recursive definition.
ƒ( ) = 0
ƒ(x) = 0
ƒ(h :: t) = h · head(t) + ƒ(t).
If-then-else form:
ƒ(L) = if L = or tail(L) = then 0 else head(L) · head(tail(L)) + ƒ(tail(L)).
*
*
Example 6. Find a recursive definition for isin : A lists(A) {true, false} where isin(x, L)
means that x is in the list L.
Solution: isin(x, ) = false
isin(x, x :: t) = true
isin(x, h :: t) = isin(x, t).
If-then-else form:
isin(x, L) = if L = then false else if x = head(L) then true else isin(x, tail(L)).
Example 7. Find a recursive definition for sub : lists(A) lists(A) {true, false} where
sub(L, M) means the elements of L are elements of M.
Solution: sub( , M) = true
sub(h :: t, M) = if isin(h, M) then sub(t, M) else false.
If-then-else form:
sub(L, M) = if L = then true else if isin(head(L), M) then sub(tail(L), M) else false.
Example 8. Find a recursive definition for intree : Q binSearchTrees(Q) {true, false}
where intree(x, T) means x is in the binary search tree T.
Solution: intree(x, ) = false
intree(x, tree(L, x, R)) = true
intree(x, tree(L, y, R)) = if x < y then intree(x, L) else intree(x, R).
If-then-else form: intree(x, T) = if T = then false
else if x = root(T) then true
else if x < root(T) then intree(x, left(T))
else intree(x, right(T)).
*
*
Graph Traversals
A graph traversal starts at some vertex v and visits all the vertices on the paths that start at v. If a vertex has already been visited, it is not visited again. It follows that any traversal of a connected graph will visit all its vertices. A depth-first traversal starts by visiting v. Then it calls itself on each vertex adjacent to v that has not already been visited. Here’s a recursive procedure to do a depth-first traversal that starts at vertex v.
D(v): if v has not been visited then
visit(v);
for each edge from v to x do D(x) od
fi
Quiz (1 minute). Find a depth-first traversal of the pictured graph that starts at F.
One answer: F, H, G, D, B, A, C, E.
Quiz (1 minute). Find a depth-first traversal of the pictured graph that starts at E.
One answer: E, D, F, H, G, A, C, B.
F
D
E
B
C
A
G
H
*
*
Traversing Binary Trees
The three standard procedures to traverse a binary tree are defined recursively as follows:
preorder(T): if T ≠ then visit root(T); preorder(left(T)); preorder(right(T)) fi.
inorder(T): if T ≠ then inorder(left(T)); visit root(T); inorder(right(T)) fi
postorder(T): if T ≠ then postorder(left(T)); postorder(right(T)); visit root(T) fi.
Example 9. Traverse the following tree in each of the three orders.
Solution:
Preorder: a b c d e
Inorder: b a d c e
Postorder: b d e c a
Example 10. Find a recursive definition for post : binaryTrees(A) lists(A) where post(T) is
the list of nodes from a postorder traversal of T.
Solution: post( ) =
post(tree(L, x, R)) = cat(post(L), cat(post(R), x ))
where cat concatenates two lists and can be defined by,
cat( , L) = L
cat(h :: t, L) = h :: cat(t, L).
a
b
c
d
e
*
*
Example 11. Find a recursive definition for ƒ : binaryTrees(Q) Q where ƒ(T) is the sum
of the nodes in T.
Solution: ƒ( ) = 0
ƒ(tree(L, x, R)) = x + ƒ(L) + ƒ(R).
Infinite Sequences
We can construct recursive definitions for infinite sequences by defining a value ƒ(x) in
terms of x and ƒ(y) for some value y in the sequence.
Example 12. Suppose we want to represent the infinite sequence ƒ(x) = x, x2, x4, x8, … .
Solution: Use the definition to discover a solution as follows:
ƒ(x) = x, x2, x4, x8, … = x :: x2, x4, x8, … = x :: ƒ(x2).
So define ƒ(x) = x :: ƒ(x2).
Example 13. What sequence is defined by g(x, k) = xk :: g(x, k + 1)?
Answer: g(x, k) = xk :: g(x, k + 1) = xk :: xk+1 :: g(x, k + 2) =… = xk, xk+1, xk+2, … .
Example 14. How do we obtain the sequence x, x3, x5, x7, … ?
A Solution. Define ƒ(x) = h(x, 1), where h(x, k) = xk :: h(x, k + 2).
Example 15. How do we obtain the sequence 1, x2, x4, x6, x8, … ?
A Solution: Use h(x, 0) from Example 14.
*
*
Section 3.3 Computer Science: Grammars
A grammar is a finite set of rules, called productions, that are used to describe the strings of
a language.
Notational Example. The productions take the form a b, where a and b are strings over
an alphabet of terminals and nonterminals. Read a b as, “a produces b,” “a derives b,”
or “a is replaced by b.” The following four expressions are productions for a grammar.
Terminals: {a, b}, the alphabet of the language.
Nonterminals: {S, B}, the grammar symbols (uppercase letters), disjoint from terminals.
Start symbol: S, a specified nonterminal alone on the left side of some production.
Sentential form: any string of terminals and/or nonterminals.
Derivation: a transformation of sentential forms by means of productions as
follows: If xay is a sentential form and a b is a production, then the replacement
of a by b in xay to obtain xby is a derivation step, which we denote by xay xby.
Example Derivation: S aSB aaSBB aaBB aabBB aabbB aabbb.
This is a leftmost derivation, where each step replaces the leftmost nonterminal.
The symbol + means one or more steps and * means zero or more steps. So we could
write S + aabbb or S * aabbb or aSB * aSB, and so on.
S aSB
S L
B bB
B b.
Alternative Short Form
S aSB | L
B bB | b.
*
*
The Language of a Grammar
The language of a grammar is the set of terminal strings derived from the start symbol.
Example. Can we find the language of the grammar S aSB | L and B bB | b?
Solution: Examine some derivations to see if a pattern emerges.
S L
S aSB aB ab
S aSB aB abB abbB abbb
S aSB aaSBB aaBB aabB aabb
S aSB aaSBB aaBB aabBB aabbBB aabbbB aabbbb.
So we have a pretty good idea that the language of the grammar is {anbn+k | n, k N}.
Quiz (1 minute). Describe the language of the grammar S a | bcS.
Solution: {(bc)na | n N}.
Construction of Grammars
Example. Find a grammar for {anb | n N}.
Solution: We need to derive any string of a’s followed by b. The production S aS can be
used to derive strings of a’s. The production S b will stop the derivation and produce the
desired string ending with b. So a grammar for the language is S aS | b.
Quiz (1 minute). Find a grammar for {ban | n N}.
Solution: S Sa | b.
Quiz (1 minute). Find a grammar for {(ab)n | n N}.
Solution: S Sab | L or S abS | L.
*
Rules for Combining Grammars
Let L and M be two languages with grammars that have start symbols A and B, respectively,
and with disjoint sets of nonterminals. Then the following rules apply.
- L M has a grammar starting with S A | B.
- LM has a grammar starting with S AB.
- L* has a grammar starting with S AS | L.
Example. Find a grammar for {ambmcn | m, n N}.
Solution: The language is the product LM, where L = {ambm | m N} and M = {cn | n N}.
So a grammar for LM can be written in terms of grammars for L and M as follows.
S AB
A aAb | L
B cB | L.
Example. Find a grammar for the set Odd, of odd decimal numerals with no leading zeros,
where, for example, 305 Odd, but 0305 Odd.
Solution: Notice that Odd can be written in the form Odd = (PD*)*O, where
O = {1, 3, 5, 7, 9}, P = {1, 2, 3, 4, 5, 6, 7, 8, 9}, and D = {0} P.
Grammars for O, P, and D can be written with start symbols A, B, and C as:
A 1 | 3 | 5 | 7 | 9, B A | 2 | 4 | 6 | 8, and C B | 0.
Grammars for D* and PD* and (PD*)* can be written with start symbols E, F, and G as:
E CE | L, F BE, and G FG | L.
So a grammar for Odd with start symbol S is
S GA.
*
Example. Find a grammar for the language L defined inductively by,
Basis: a, b, c L.
Induction: If x, y L then ƒ(x), g(x, y) L.
Solution: We can get some idea about L by listing some of its strings.
a, b, c, ƒ(a), ƒ(b), …, g(a, a), …, g(ƒ(a), ƒ(a)), …, ƒ(g(b, c)), …, g(ƒ(a), g(b, ƒ(c))), …
So L is the set of all algebraic expressions made up from the letters a, b, c, and the function
symbols ƒ and g of arities 1 and 2, respectively. A grammar for L can be written as
S a | b | c | ƒ(S) | g(S, S).
For example, a leftmost derivation of g(ƒ(a), g(b, ƒ(c))) can be written as
S g(S, S) g(ƒ(S), S) g(ƒ(a), S) g(ƒ(a), g(S, S))
g(ƒ(a), g(b, S)) g(ƒ(a), g(b, ƒ(S))) g(ƒ(a), g(b, ƒ(c))).
A Parse Tree is a tree that represents a derivation. The root is the
start symbol and the children of a nonterminal node are the symbols
(terminals, nonterminals, or L) on the right side of the production
used in the derivation step that replaces that node.
Example. The tree shown in the picture is the parse tree for the
following derivation:
S g(S, S) g(ƒ(S), S) g(ƒ(a), S) g(ƒ(a), b).
S
g ( S , S )
ƒ ( S ) b
a
*
*
Example. Is the grammar S SaS | b ambiguous?
Solution: Yes. For example, the string babab has two distinct
leftmost derivations:
S SaS SaSaS baSaS babaS babab.
S SaS baS baSaS babaS babab.
The parse trees for the derivations are pictured.
Ambiguous Grammar: Means there is at least one string with two distinct parse trees,
or equivalently, two distinct leftmost derivations or two distinct rightmost derivations.
Quiz (2 minutes). Show that the grammar S abS | Sab | c is ambiguous.
Solution: The string abcab has two distinct leftmost derivations:
S abS abSab abcab and S Sab abSab abcab.
Unambiguous Grammar: Sometimes one can find a grammar that is not ambiguous for
the language of an ambiguous grammar.
Example. The previous example showed S SaS | b is ambiguous. The language of the
grammar is {b, bab, babab, …}. Another grammar for the language is S baS | b. It is
unambiguous because S produces either baS or b, which can’t derive the same string.
Example. The previous quiz showed S c | abS | Sab is ambiguous. Its language is
{(ab)mc(ab)n | m, n N}. Another grammar for the language is
S abS | cT and T abT | L.
It is unambiguous because S produces either abS or cT, which can’t derive the same string.
Similarly, T produces either abT or L, which can’t derive the same string.
S
S a S
S a S
b
b
b
S
S a S
S a S
b
b
b
*