Mathematical Techniques for Computer Science (COMP11120)
Class notes
Lecture Notes on Recursion for Syntax and The Natural Numbers (COMP11120)
6 views 0 purchase
Course
Mathematical Techniques for Computer Science (COMP11120)
Institution
The University Of Manchester (UOM)
Unlock the power of recursion with these detailed lecture notes for COMP11120. Covering essential topics such as recursive definitions, applications in syntax, and the properties of natural numbers, these notes offer clear explanations and practical examples to solidify your understanding.
Ideal...
Mathematical Techniques for Computer Science (COMP11120)
All documents for this subject (9)
Seller
Follow
jpxoi
Content preview
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
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.57. You're not tied to anything after your purchase.
