Lecture Notes on Recursion for Syntax and The Natural Numbers (COMP11120)

Recursion for Syntax and The Natural Numbers

Syntax and recursion :
Logic

Propositional Formulae are defined recursively ! Example of a recursively defined operation : boolean interpretation

base case If p is a
propositional atom ,
then p is a
formula
Let be valuation that 10 13 to each prop variable
Step .
case
If A is a formula ,
then -A is a
formula v a assigns a value in , .




·
If A B ,
are
formulae ,
then o
AvB Can define Iv : Set of all prop formulae > 10 1),




·
An B base case Irp =
up

·
A > B Step Cases < [v(1A) = LIVA


are
formulae .
v
[v(AvB) = IvA v IrB


1 [v(AnB) =
IvA n lvB


< Iv(A >
B) = IvA > IvB




Syntax and recursion : Formal Languages

Example Pattern : (or regular expression) over alphabet Example : The
property of a
string matching a pattern is recursive




base cases &O is a
pattern base cases & E matches E

E G is a pattern X xEE matches X

X Forxe[ ,
X is a
pattern Step cases - If s, matches p , and se matches Pe then Sisa matches (pipal
,



Step cases + If P , PC are patterns , then so is (PIPa) If s matches p , then
s matches P, /P2

If p , pC are patterns , then so is (P /Pa) , If s matches pa then
s matches P, /P2
,


If pattern then (P )
*
*
p
is a
,
so is *
If ne I and Sy up to Sn pr then
match SiSa ...
In matches pX
What if n = 0 ?

> 3 matches p*




Example : Consider the following definition mapping patterns over [ to subsets of IR




I
base cases 20 = O

-LE =
43] Can prove by induction :

x2x =
(2) Prop Lp =
[SE ** Is matches pl
oncatonation
.




Step cases
+
h(pipa) =
Lp . .
2 c =
455/st2 se2) ,



[(p /Pa)
.
=
Lup u Lp
, &* =
(5 ,
...

Sn nEIN ,
SitL]
*((p*) =
(2p) *



Further examples of recursive constructions ·
Recursion is a
very useful way of defining syntatic expressions of arbitrary leught
·
string generated by a
grammar
·
Can then also use recursion to help us
give meaning to such expressions.

· The While language :
· arithmetic expressions ·
Can then use induction to prove properties of such expressions operations or properties for these.
·
boolean expressions

·
statements
·
Execution of While
a
program
·
Derivations of Hours triples for While programs