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
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
