Theory of Computation

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

Click the above link for details.

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, …}

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

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>::= .

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
   

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

• A syntax diagram uses the following three symbols:

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

• 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

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

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