Transcript Discrete Structure - Open University of Hong Kong

Discrete Structure
Li Tak Sing(李德成)
Lectures 14-15
1
Recursive functions for binary tree
Let "nodes" be the function that returns the
number of nodes in a binary tree.
Using the pattern matching form
nodes(<>)=0
nodes(tree(L,a,R))=1+nodes(L)+nodes(R)
Using the if-then-else-form
nodes(T) = if T=<> then 0
else
1+nodes(left(T))+nodes(right(T))
fi
2
Binary search tree
 Let 'insert' be a function that accepts two
parameters, x and a binary search tree. The
function returns another binary search tree so
that x is inserted into the original tree.
 insert(x,<>)=tree(<>,x,<>).
 insert(x,tree(L,a,R))=if (x<a) then
tree(insert(x,L),a,R)
else
tree(L,a,insert(x,R))
3
Binary search tree
Another form:
insert(x,T)= if T=<> then tree(<>,x,<>)
else if x<root(T) then
tree(insert(x,left(T)),root(T), right(T))
else
tree(left(T),root(T), insert(x,right(T)))
4
Traversing Binary Trees
Preorder traversal
The preorder traversal of a binary tree starts by
visiting the root. Then there is a preorder
traversal of the left subtree
Preorder procedure
Preorder(T): if T<> then
print(root(T));
Preorder(left(T));
Preorder(right(T));
fi.
5
A preorder function
A preorder function is defined below:
preOrd(<>)=<>,
preOrd(tree(L,x,R))=x::cat(preOrd(L),preOrd(R)
)
6
Inorder traversal
 The inorder traversal of a binary tree starts with
an inorder traversal of the left tree. Then the root
is visited. Lastly there is an inorder traversal of
the right subtree.
 Inorder procedure
Inorder(T): if T<> then
inorder(left(T));
print(root(T));
inorder(right(T));
fi.
7
Inorder function
A inorder function is defined below:
preOrd(<>)=<>,
preOrd(tree(L,x,R))=cat(preOld(L),x::preOld(R))
8
postorder traversal
The postorder traversal of a binary tree
starts with a postorder of the left subtree
and is followed by a postorder traversal of
the right subtree. Lastly the root is visited.
9
Example.
Write a recursive definition for the
procedure P such that for any binary tree
T, P(T) prints those nodes of T that have
two children, during inorder traverse of the
tree.
Write down a recursive procedure to print
out the leaves of a binary tree that are
encountered during an inorder traverse of
the tree.
10
The repeated element problem
To remove repeated elements from a list.
remove(<a,b,a,c>)=<a,b,c>
Only the left most repeated element is
kept.
To find the solution, lets consider a list
with head H and tail T.
The function can be done by removing all
occurrences of H in T and then
concatenate H with that result.
11
The repeated element problem
So the remove function can be defined as:
remove(<>)=<>
remove(H::T)=H::remove(removeAll(H,T))
We have assumed the existence of a function
removeAll which will remove all the occurrences
of H in T.
For example removeAll(a,<a,b,a,c,d>)
would return <b,c,d>
12
removeAll
removeAll(a,<>)=<>
removeAll(a,a::T)=removeAll(a,T)
removeAll(a,H::T)=H::removeAll(a,T)
13
removeAll
removeAll(a,M)=
if M=<> then <>
else if a=head(M) then
removeAll(a,tail(M))
else
head(M)::removeAll(a,tailM))
14
Grammars
A set of rules used to define the structure
of the strings in a language.
For example, the following English
sentence consists of a subject followed by
a predicate:
The big dog chased the cat
subject: The big dog
predicate: chased the cat
15
Grammar
The grammar of the sentence is:
sentence subject predicate
The subject phase can be further divided
into an article, an adjective and a noun:
subject  article adjective noun
so article=this, adjective=big, noun=dog
16
Grammer
Similarly, the predicate can have the
following rule:
predicate  verb object
verb=chased, object=cat
17
Structure of grammas
If L is a language over an alphabet A, then
a grammer for L consists of a set of
grammer rules of the form

where  and  denotes strings of symbols
taken from A.
18
Structure of grammas
The grammar rule  is often called a
production, and it can be read in several
different ways as
replace  by 
 produces 
 rewrites to 
 reduces to 
19
Start symbol
Every grammar has a special grammar
symbol called the start symbol, and there
must be at least one production with the
left side consisting of only the start
symbol. For example, if S is the start
symbol for a grammar, then there must be
at least one production of the form:
S
20
An example
S
SaS
SbS
ScS
All strings that consists of a, b and c.
21
Definition of a Grammar
 An alphabet N of grammar symbols called
nonterminals.
 An alphabet T of symbols called terminals. The
terminals are distinct from the nonterminals.
 A specific nonterminal S, call the start symbol.
 A finite set of productions of the form ,
where  and  are strings over the alphabet
NT with the restriction that  is not the empty
string. There is at least one production with only
the start symbol S on its left side. Each
nonterminal must appear on the left side of
some production.
22
Grammar
When two or more productions have the
same left side, we can simplify the
notation by writing one production with
alternate right sides separated by the
vertical line |. For example, the last
grammar can be rewritten as:
S  | aS | bS | cS
23
Grammars
A grammar is a 4-tuple. G=(N,T,S,P)
N: non-terminals,
T: terminals,
S: start symbol,
P: rules
In the last example, we have
G=({S},{a,b,c},S,{S  | aS | bS | cS
})
24
Derivations
A string made up of terminals and
nonterminals is called a sentential form.
If x and y are sentential forms and  is
a production, then the replacement of  by
 is called derivation, and we denote it by
writing
xyxy
25
Derivations

+
*
derives in one step
derives in one or more steps
derives in zero or more steps
26
Examples in derivatives
S=AB
A=|aA
B= |bB
SAB AbB Ab aAb aaAb aab
27
Rightmost and leftmost derivation
 It is possible to find several different derivations
of the same string.
 For example, we can have
S AB AbB Ab aAb ab
S AB aAB aB abB ab
 A derivation is called a leftmost derivation if at
each step the leftmost nonterminal of the
sentential is reduced by some production.
Similarly, a derivation is called a rightmost
derivation if at each step the rightmost
nonterminal of the sentential form is reduced by
some production.
28
The language of a grammar
 If G is a grammar, then the language of G is the
set of terminal strings derived from the start
symbol of G. The language of G is denoted by
L(G).
 The formal definition is:
If G is a grammar with start symbol S and set of
terminals T, then the language of G is the set
L(G)={s | sT* and S+s}
29
Recursive production
A production is called recursive if its left
side occurs on its right side. For example,
the production SaS is recursive.
A production A  is indirectly recurisve if
A derives a sentential form that contains
A.
30
Recursive production
For example:
Sb|aA
A c|bS
The productions S aA and A bS are both
indirectly recurisve:
SaA abS
A bS baA
31
Recursive grammar
A grammar is recursive if it contains either
a recursive production or an indirectly
recursive production.
A grammar for an infinite language must
be recursive.
32