Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMP11212: Fundamentals of Computation - Coggle Diagram
COMP11212: Fundamentals of Computation
Describing languages to a computer
Formal Languages
Formal languages consist of words whose letters are taken from an alphabet and are well formed according to a specific set of rules
Languages are sets of words which are sequences of symbols
Symbols are letters, digits, protagonists etc
Alphabets are sets of symbols that we use to construct words
A word (string) is formed by concatenating other words or letters
Languages are sets so they can be operated on to create new sets thus languages
Operators are: concatenation, union, \, ', ., *
Regular Expressions
All finite sets of words are regular and if you perform an operation on a regular language, you get a regular language
Regular expressions allow us to describe languages in terms of patterns
This allows us to apply an inductive argument when proving theorems about our definitions
Languages are recursively defined from the base cases of the empty words and have operations performed on it
Regular languages are not rare and there are ways of building them, but not all languages of interest are regular
The alternative operator is commutative, but concatenation is not
How do we come up with patterns?
Using pictures
Finite State Automata
Every automaton consists of
states
an initial state
a number of possible accepting states
The transition function takes as input states and letter and outputs a state
People also refer to a finite state machine
DFAs
We can view a DFA as defining a language
For every particular word, there is precisely one path through the automaton. We have to read off if we are in an accepting state or not. Therefore, these are called deterministic automata.
These have a number of states, including a start state and accepting states. You don't have to include the dump or unreachable states
The transitions for a DFA are a function. A DFA can be considered as a NFA.
DFAs must have an initial state, but not an accepting state
NFAs
The transition for an NFA are a relation. For every NFA we can define a DFA that accepts precisely the same language.
For NFAs, there is no longer a unique path for each word. We say that the automaton accepts the word if there is at least one such path that ends in an accepting state.
NFAs must have an initial state, but not an accepting state or transitions.
DFAs vs NFAs
It is usually easier to design a NFA and the resulting automata are often smaller
Following a word through a DFA is straightforward, but NFAs have multiple paths
Every deterministic automaton can be viewed as a non-deterministic and there are not things we can do with NFAs that can't be done with DFAs
We can create a DFA from an NFA by:
Having the state of the new automaton are sets of states from the old one
The start state for the new automaton is the set containing just the initial state from the original automaton
A state of the new automaton is an accepting state if one of its states in the old automaton, is an accepting state
There are transitions between states that replicate the old automaton
Note that the state given by the empty state is always a 'dump state'
It is possible to avoid drawing unreachable states by
DFA to RegEx
Loops make creating Regex from automata more difficult
There is an equation for finding the RegEx. Try and label the most complex state with the highest number.
NFA + epsilon transistions
These allow for transitive labelled with epsilon, and can be transformed to an NFA
Regex to NFA +epsilon
We have an algorithm that will take a regular expression and produce an NFA+epsilon that will accept precisely those words that match the RegEx
Regular Languages
The language is regular if it is the set of all words matching some regular expressions
The set of Regular Languages is closed under union, concatenation and Kleene star, intersection, reversal and complement
From automata to patterns:
We have three ways of talking about collections of string or languages
Set theoretically
RegEx
N/DFA
In order to show that it is still possible to construct a regular expression defining the same language for every automaton we have to give an algorithm that works for all automata
Patterns to automata
For epsilon transitions
If we can reach an accepting state using only e-transitions, we make this state accepting
If we can get from state j to u, using epsilon and the symbol, we can replace it with the letter
Equivalence of Automata
Simulations
A bi-simulation shows that two automata accept exactly the same language
Non-existence of a simulation does not mean non-equivalent
Two automata are equivalent if they accept the same language. A simulation is a way of relating the states of two automata.
Minimisation
A unique minimisation is only guaranteed for DFAs and two DFAs are equivalent if they result in the same minimisation
Table Filling
Accepting states are distinguishable from non-accepting
Non-regular languages
Languages that require counting or balancing are not regular
The pumping lemma is a result that allows us to conclude non-regularity for some languages
Properties of regular languages
Concatenation, Kleene Star, Reversal, Unions, Intersection, Complements, Reversal via Induction Proof
Describing more complicated languages
Grammars
A context-free grammar is given by alphabets of terminal and non-terminal symbols, a start symbol and production rules
They are more powerful and expressive ways of describing languages.
The set of Regular Languages over an alphabet is a strict subset of the set of CFLs
Parsing
A Parse Tree shows how a string may be generated from a grammar. An ambiguous grammar is one where there are strings that have multiple parse trees.
Ambiguous grammars have multiple paths for the same strings
An unambiguous grammar would be the one taken from the DFA as there is only one parse tree for each word.
CFLs are closed under concatenation, union, Kleene star and reversal, but not under intersection
A CFL is generated by a Context Free Grammar. There are no cycles in some languages created by grammars, therefore we have finite languages
Regular expressions are not sufficient to describe all the languages we are interested in.
A programming language
To define a program we have to define its syntax and semantics. The syntax of a language tells us how to write programs that are considered well-formed
Operations on CFLs
Concatenation, Kleene star, Reversal, Unions
Limitations of context-free languages
Some counting words are not context free
There are automata which can be used to describe the context-free languages, which are known as pushdown automata. These have a memory device that takes the form of a stack, but deterministic and non-deterministic versions are not equivalent.
Recap and Intro
Not all functions have an inverse. We can use the notion of inverse function to give an alternative definition of bijection
Complexity - which program runs faster?
Correctness - correctly computing a function
Computability - what functions can we compute
Computation
Abstract Perspective - Perform some operation, manipulate some symbols
Practical Perspective - Processor that executes instructions, stores data in registers
Complexity
which is better
which is faster
time complexity
Correctness
Is the code correct?
Syntax errors
Logic errors
Need a spec
Computability
Prove that there are un-computable function
Sensible models of computation are equivalent
Some languages are universal and they can implement each other
The while Programming Language
State in which current values of the variables are stored. We ensure there is only one value associated with each variable
A Transition System for Statements
configuration <S, o>, where the first is a program and the other is a state
To rewrite a configuration, we execute the first statement and make changes to the state
Meaning of a program
Operational
Define what it means to interpret/execute programs
Axiomatic
Define a program by what it provably done
Denotational
Transform program into some other metalanguage
While programs do not always terminate
If a program runs and produces an output it does not have to be correct
Coding and Counting Programs
Countability
natural numbers are countable
real numbers are uncountable
integers are countable
pairs of natural numbers are countable
functions from natural numbers to natural numbers are countable
The while programs are countable. We can code functions in arbitrary (countable) domains in natural numbers to natural numbers
We can show that the while programs are countable by showing that there is a bijection between functions of integers and functions of natural numbers
For a pairing between X and Y to be a bijection, for properties must hold:
Each element of X must be paired with at least one element of Y
No element of X may be paired with more than one element of Y
Each element of Y must be paired with at least one element of X
No element of Y may be paired with more than one element of X
Bijections
For Z -> N we can map positive numbers to even numbers and negative numbers to odd. We can show that this is reversible and therefore a bijection
We can define a bijection to code our statements in while in N
The valid ways of showing that a function is a bijection are:
showing that it is both injective and surjective
showing that it has an inverse
Operations on Structures as Arithmetic
We are able to encode pairs and lists as natural numbers we can argue that we do not need these structures in our language to be able to represent programs that are these structures.
By showing that arbitrary data structures can be coded as natural numbers we can convince ourselves that we only need to consider programs on natural numbers
Counting programs
We can count or enumerate while programs by introducing a bijection between statements of the while language and N
We can encode arithmetic expressions, boolean expressions and statements and natural numbers
We call these code numbers or Gödel numbers
The set of while programs is effectively countably infinite. The term effective in maths means that we have a method for doing it so if a set is effectively countable then we have a procedure for counting the elements of the set.
Complexity and Asymptotic Analysis
Complexity
a measure of the resources required to execute the program
by default we discuss time (i.e. efficiency)
Two programs can complete the same function with different complexities, but we maybe interested in the inherent complexity of a problem itself
When we talk about programs, we will usually think in terms of upper bounds and when we talk about problems we talk about lower bounds
How long does a program take to execute?
We count arithmetic, checks, memory
Operation time is architecture dependent
The number of times the loop goes around depends on the input
The time complexity we care about (Best, Worst, Average, Common Case) depends on the situation
Asymptotic analysis or Order of Growth
Problems with counting
It is necessary to consider many different cases
There is no easy way to analyse sub-components and combine the results
Different compilers or compiler options might affect the results
The exact operation count end up being complicated
We can ignore any constants in our calculations
We say that a function g dominates another f whenever there exists k:N if g(n) > f(n)
This observation allows us to ignore terms in a function that are eventually dominated by another, bigger term in that function
We have said that we can view any polynomial function f of order/degree k as having the same complexity as the function nk as there will always be a constant C such that cn^k will eventually dominate f,
Instead we capture Order of Growth with Big-O notation
Simplifying assumptions
We assume that all accesses occur in constant time
We measure the usage of some resource but the units that we measure will have a significant impact on the result
We need to decide which operation matter and what their associated cost should be.
The instructions or operation that we measure, us an informed choice made by the computer scientists. Ideally this choice should be made so that the results obtained are useful.
Properties of Big-O
O(1) and O(n) are shorthand for the polynomial function f(n) = 1 and f(n) = n
O(1) < O(n) i.e. is a strict subset
Even though one function may dominate another, this may not be practically relevant
Loops do not necessary imply certain complexity. If they are not influenced by input, they can have a constant time
This demonstrates a limitation of asymptotic complexity and a warning about counting loops
Lower Bounds
Big-Omega notation
If the function f is a subset of the omega notation of g, we are saying that eventually the function f dominates g i.e. g is a lower bound to f
Algorithms have an upper bound on their execution time and problems have a lower bound
The existence of a difference between best algorithm and the problems lower bound is called the algorithmic gap
Space complexity
This is how much memory it requires to run
We are less concerned with this as space requirements are often less dependent on the size of the input and in many cases are fixed and we have more space than time.
Space complexity cannot be larger than time complexity if we assume that everything that is written to or read from the used space takes some time to do so.
Complexity Classes
A complexity class is a set of functions (problems) with the same asymptotic complexity. A complexity class P as the set of all polynomial. We usually call problems in P tractable and those not in P intractable i.e. not practically solvable.
Non-deterministic Polynomial classes are when a non-deterministic machine could compute that function in polynomial time. All probelms in P are in NP, but we're not clear on the other way around.
You can show a problem is in a particular class through reduction
Big-O describes the set of all algorithms than run no worse than a certain speed (upper bound)
Big Omega describes the set of all algorithms that run no better than a certain speed (lower bound)
Big Theta describes the set of all algorithms that run at a certain speed (equality or tight bound)
Proving while Programs Correct
Intro to Correctness
Well-behaved with respect to Language Properties
Properly Typed
whether it type checks
Semantic Correctness
intended outcome - the intended outcome was implicit in the programming language. Now we need to make it explicit by writing it down
Termination
whether a program should or should not terminate. For programs that don't terminate we want to establish other properties, such as progress and fairness
Syntactic Wellformedness
the program needs to be checked against the grammar
A program is only correct or incorrect with respect to a given spec
We prove correctness using a specification of what we want it to do and a method for checking whether the program meets the specification i.e. with Hoare Logic
The intended behaviours of a program can be captured by using two predicates: Pre for precondition, Post for postcondition, which should both be satisfied.
The problem with checking correctness of P with respect to Pre and Post is then the problem of checking whether Spec(pre, Post) is in Actual(P)
If we do not consider non-terminating runs then this is partial correctness. Otherwise it is necessary to ensure that all runs terminate - total correctness.
A loop invariant is a predicate P which is true at the start and end of each execution of a while-loop body
A loop variant is a quantity v which strictly decreases on every iteration of the while loop and is bounded below by b i.e. when it reaches a certain value the while-loop will terminate
Axiomatic System for Partial Correctness
This gives us a structural way in which to present our reasoning about programs
A Hoare Triple {P}S{Q} for partial correctness is a triple consisting of two predicates and a statement. If we start in a state satisfying P, execute S and end up in a state satisfying Q.
We introduce a proof system that allows us to establish the validity of Hoare Triples
The triple {false}S{Q} is always true for any program S and postcondition Q. The triple {P != false}S{false} is always false for terminating programs and true for non-terminating programs
The partial correctness property is "If the precondition is true of the initial state, and the statement S terminates, then the post-condition must be true of the final state". If the program does not terminate, the postcondition may be true or false.
Proving partial correctness requires two steps:
generating loop invariant
applying the rue of consequence to put things together
We use precondition strengthening and postcondition weakening
Total Correctness
We prove that every loop must terminate then we say that the program is totally correct with respect to the pre and post conditions
We use the Hoare Triple [P]S[Q] for total correctness
Guidance on Proofs of Correctness
There is no general algorithm as the correctness problem is undecidable. Many parts are algorithmic, the while requires a loop invariant for partial correctness and a loop variant for total correctness. The rule of consequence doesn't tell you when to apply it.
For total correctness one just needs to add the loop invariant in the appropriate place.
If there is a loop, find a loop invariant R, if it is a total correctness specification find a loop variant also.
Deal with the bits of the program before and after the loop
Produce a proof for the loop body
Computability
A function is computable iff there is a while program such that for all states o and n in the natural numbers with o(x) = n, then if there is some state o' such that <S, o> ->* o' then o'(x) = f(n) i.e. A function from the natural form N -> N is computable if we can write a while program to implement the function. This allows for computable partial functions.
Un-computable functions
There are infinitely many functions N -> N
If we assume that we can enumerate all of the functions in N -> N, it turns out that we cannot, because there is a missing function
Therefore we have uncountably many functions N -> N
There are only countably many programs and many functions for which there is no while program
Decidability
We can partition N-> N into computable and non-computable. We can also use simpler data structures than the natural numbers. There is a special class of function you should already be familiar with: boolean functions or predicates.
Functions which return boolean values are called predicates. They are also decidable. A decidable predicate is computable.
A total function f is called the characteristic function of P, and the associated program in while is a decision procedure for P.
f(x) = { 1 if P(x) holds, 0 if P(x) doesn't hold
A function that is defined in terms of any other functions is computable as long as those functions are computable and the check required
The program for a decidable predicate always terminates. Partially-decidable describes the situation where we can determine whether something is true.
Universality of Computation
A program computes exactly one function but a function can be computed by many functions. Every program has a unique index given to it by gamma, the function that this program computes is not unique
The Universal Program is a program which can simulate every other program
The Halting Problem
No matter the result, we can generate a contradiction, showing it is impossible to write a halt tester in our while language
No Turing-equivalent computer can implement a halt-testing program,
There is a difference between the following statements
There exists a program P that decides whether every program Q halts
For all programs Q there exists a program P that decides whether Q halts
We can choose a second program to decide that a specific program halts.
The Church-Turing Thesis
A Turing-Machine is a finite device which performs operations on an infinite tape. The machine has a state and a finite set of rules that show how the machine makes transitions between states.
Any sensible definition of computation will define the same functions to be computable as any other definition