Theory of Computation

Table of Contents

1 Abstraction and Automation

Problem Solving Using Algorithms

Computer science is about building clean abstract models (abstractions) of messy, noisy, real world objects or phenomena. Computer scientists have to choose what to include in models and what to discard, to determine the minimum amount of detail necessary to model in order to solve a given problem to the required degree of accuracy.

Computer science deals with putting the models into action to solve problems. This involves creating algorithms for performing actions on, and with, the data that has been modelled.

Algorithms

  • A finite steps of instrcution/steps to solver a specific problem; Algorithms can be expressed in the following forms:
    • Flowchart
    • Psuedo-code
    • Structured English
  • Algorithms employ with the standard constructs:
    • sequence
    • assignment
    • selection
    • iteration
  • Dry run an algorithms means to the programmer working through a program on paper, usually using a table called a 'trace table'.
  • To test a solution, there needs to be a set of test data that will thoroughly test the solution:
    • typical/normal/valid data: the solution expected data including type and range
    • extreme/boundary data: Data that is on the extreme limits of the range but should be accepted e.g. if the validation says that price <=£100 then £100 should be tested as that is right at the upper limit.
    • erroneous/invalid data: the solution should output error for those data; either because of wrong type or exceeding the limits.

Abstraction

Abstraction can be achieved by:

  1. representational abstraction: a representation arrived at by removing unnecessary details
  2. abstraction by generalisation or categorisation: a grouping by common characteristics to arrive at a hierarchical relationship of the "is a kind of" type.

Procedural abstraction:

  • Disregards the actual values, the result of a procedural abstraction is a procedure/computational method, not a function. To get a function requires yet another abstraction, which disregards the particular computation method. This is functional abstraction.

Data abstraction:

  • details of how data are actually represented are hidden, allowing new kinds of data objects to be constructed from previously defined types of data objects.
  • For example, a stack could be implemented as an array and a pointer for top of stack. A tree can be implemented as three arrays with one for the left pointer, one for the right pointer and one for the nodes' values.

Problem abstraction:

  • Details are removed until the problem is represented in a way that is possible to solve because the problem reduces to one that has already been solved.

Decomposition:

  • Procedural decomposition means breaking a problem into a number

of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided. Composition:

  • A composition abstraction means combining procedures to form compound

procedures.

  • Data abstraction composition means combining data objects to form compound data, such as the afore-mentioned tree data structure made of three arrays.

Automation

Automation means putting models (abstraction of real world objects/ phenomena) into action to solve problems. This is achieved by:

  • creating algorithms
  • implementing the algorithms in program code (instructions)
  • implementing the models in data structures
  • executing the code.

2 Regular Languages

Finite State Machine(FSM)

Click the above link for details.

Regular Expression

A regular expression is simply a way of describing a set. Regular expressions allow particular types of languages to be described in a convenient shorthand notation.

  • ? 0 or one match
  • * 0 or more match
  • + 1 or more match
  • | or, for example a|b means a or b
  • . any character
  • \d any digit
  • \w any alphanumeric character
  • \s any white space
  • Examples:
    • ab* generate the set of strings {a, ab, abb, abbb, …}
    • ab? generates the set {a,ab}
    • a+b+ generates the set {ab, aab,aaab,…,abb,abbb,…}
    • a(a|b)* generates the set of strings {a, aa, ab, aaa, aab, aba, …}

Regular Language

  • a language is called regular if it can be represented by a regular expression.
  • a regular language is any language that a FSM will accept.
  • a string is said to be part of a language if it is accepted by a FSM that describes the rules of the language.
  • Follow this link to see how regular languages can be described using FSM and regular expressions.

3 Context-free languages

Backus-Naur Form (BNF)

Programmng languages need to follow a set of standard syntax or grammer rules to be translated into machine code. Those rules must be defined unambiguously. Natural languages such as English are not precise and computers cannot under natural languages precisely.

Defining the syntax of a language

  • Regular expressions can be used to define some simple syntax rules. But for some programming language constructs, for example, valid variable names, nested brackets, it is impossible or lengthy to use regular expression.
  • Backus-Naur Form is a meta language used to define the syntax or grammer rules of programming languages. BNF uses the following meta symbols:
    • ::= means "is defined by"

      example: <digit> ::= 0|1|2|3|4|5|6|7|8|9 which means a digit is defined by 0,1,2,3,4,5,6,7,8,or 9

    • <digit> is called a meta component or syntactic variable

Other often used meta components:

  • <letter> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|o|q|r|s|t|u|v|w|x|y|z
  • <point>::= .

Backus-Naur Form (BNF) Examples

  1. Example 1
    Write the BNF definition for a language that a valid variable name
    consisting of either a single letter or a letter followed by a digit.
    
    <variableName> ::= <letter>|<letter><digit>
    <letter> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|o|q|r|s|t|u|v|w|x|y|z
    <digit> ::== 0|1|2|3|4|5|6|7|8|9
    

Using recursion in BNF

BNF uses recursion when appropriate where a statement is defined in terms of itself. Example 2 is such as case.

  1. Example 2
    Write the BNF definition for a positive integer.
    
    <positiveInteger> ::= <digit>|<digit><positiveInteger>     <--recursion
    <digit> ::== 0|1|2|3|4|5|6|7|8|9
    
  1. Example 3
    Write the BNF definition for a hex.
    
    <hex> ::= <digit> | <letter> | <digit><hex> | <letter><hex> <-- recursion
    <digit> ::== 0|1|2|3|4|5|6|7|8|9
    <letter> ::= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|o|q|r|s|t|u|v|w|x|y|z
    

Syntax Diagram

Syntax diagram is a graphic representation of syntax rules, and it can be mapped to BNF.

  • A syntax diagram uses the following three symbols:

syntaxDigramSymbols.png

  • Using the above symbol, the previous example on positive integer can be represented using syntax diagram as below:

syntaxDigramPositiveInteger.png

4 Classification of algorithms

Comparing Algorithms and Big-O notation

  • Algorithms can be compared by expressing their complexity as a function relative to the size of the problem. The size of the problem is the key issue.
  • The efficiency of algorithms can be evaluated based on:
    1. time: how long or how many operations
    2. space: the amount of memory taken

Complexity of algorithms in terms of functions:

  • a linear function, for example y = 2x
  • a polynomial function, for example y = 2x2
  • an exponential function, for example y = 2x
  • a logarithmic function, for example y = log10 x
  • a factorial function, for example y = x!

Big-O notation: the time complexity of algorithms

The time required to run an algorithm can be (in the order from least time to most time needed):

  • constant time: O(1)
    • Regardless of the size of the data, the time will be the same to run the algorithm. For example: len(myArray)
  • logarithmic time: O(logn)
    • the algorithms will increase the amount of time very slowly as the data set increases.
    • Example: binary search - search a sorted list for a value by comparing with the middle value in the data set, thus reducing the data set by half each time.
  • linear time: O(n)
    • the algorithms take the amount of time that is directly proportional to the size of the input data set.
    • Examples: linear search
  • polynomial time: O(n2)
    • the algorithms take the amount of time that is directly proportional to the square of the size of the input data set.
    • Examples: Bubble sort and nested loops for a 2D array.
  • exponential time: O(2n)
    • this means for each added item, the algorithms will double the amount of time.
    • Examples: Fibonacci sequence with recursion.

BigOComparison.png

5 Optimisation algorithms

Dijkstra’s shortest path algorithm

  • Dijkstra's algorithm is an iterative algorithm that finds the shortest path from one particular starting node to all other nodes in a given graph.

Dijkstra.png

  • from the above example, from A, the shortest path:
    • to B is A, B
    • to C is A, B, D
    • to D is A, B, D
  • Here is a youtube video to help you.

6 A model of computation

Turing Machine

  • A Turing machine is a hypothetical machine thought of by the mathematician Alan Turing in 1936. Despite its simplicity, the machine can simulate ANY computer algorithm, no matter how complicated it is.
  • Turing machines provide a (general/formal) model of computation and provide a definition of what is computable (able to solve a problem effectively).
  • A Turing machine can be viewed as a computer with a single fixed program, expressed using:
    • a finite set of states in a state transition diagram
    • a finite alphabet of symbols
    • an infinite tape with marked-off squares
    • a sensing read-write head that can travel along the tape, one square at a time.
    • One of the states is called a start state and states that have no outgoing transitions are called halting states.
  • Here is a youTube video explaining a Turing machine:

Transition Function

  • a transition function defines the rules for state changes. It can be expressed as following:
    δ(Current State, Input Symbol) = (Next State, Output Symbol, Movement)
    
    • The state can be denoted as S1, S2 etc
    • The symbol for input and output are one of a finite set of symbols
    • The movement can be left, right on the tape to the current position/squre.
    • The transition function is equavilent to a program on a computer while the tape can be liked to a computer's main memory.