3-1-6 Regular Expressions, BNF & RPN

Natural Language comprises of:

• Set of words
• Syntax - rules for putting words together
• Semantics - meaning

e.g. The peanut ate the monkey

• Syntax - correct
• Semantics - incorrect

Formal Language comprises of:

• Alphabet
• Syntax
• No semantics

e.g. Postcode (PO12 4JH)

Meta Language (rules of formal language) comprises of:

• Regular Expressions
• Backus-Naur Form

Regular Language - one that can be expressed as a FSA (non-determistic finite state machine)

Regular Expression - describes valid strings in a formal language

Example:

a(a│b)*       

│ = or      * = Zero or more occurences

Valid  a  aa  aabab

Invalid  b  ba  abc

Notation:

* - Zero or More  a*

│ - Or  a│b

+ - One or More  a+

? – Zero or One  aab?

More notation (meta characters):

( )   - Brackets

[ ]   - Alternate OR  [ab]

-     - Sequence  a-z

^    - Not  ^t

\    - Escape Meta Meaning or Shorthand Classes 

.     - Wildcard Character

Backus-Naur Form - notation for expressing the rules for constructing valid strings in a regular language.

3-1 Problem Solving

3-1-1 Information & Hiding
3-1-2 Comparing Algorithms
3-1-3 Finite State Machines
3-1-4 Turing Machines
3-1-5 Intractable Problems
3-1-6 Regular Expressions, BNF & RPN

3-2-6 Searching and Sorting

Linear Search: this method starts at beginning of a list and compares each element in turn with the required value until a match is found or the end of the list is reached.

Bubble Sort: during a pass through the list, neighbouring values are compared & swapped if they are not in the correct order. Several passes are made until one pass does not require any further swaps.

 

Binary Search Example





















Binary Search: the algorithm is quite simple. It can be done either recursively or iteratively:

1. get the middle element;
2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
• searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
• searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.

Insertion Sort Example

Insertion Sort: An O(n²) sorting algorithm which moves elements one at a time into the correct position. The algorithm consists of inserting one element at a time into the previously sorted part of the array, moving higher ranked elements up as necessary. To start off, the first (or smallest, or any arbitrary) element of the unsorted array is considered to be the sorted part.

3-1-5 Intractable Problems

Types of Problems:

• (1) Algorithmic & (2) Non-Algorithmic

(1) These can be solved using rules or a series of steps. e.g. baking a cake
(2) These cannot be solved using rules or a series of steps. e.g. who would win in a fight between batman and superman

• (1) Finite & (2) Infinite

(1) Finite set of inputs and are solvable.
(2) Infinite set of inputs and are not necessarily solvable.

• (1) Computable & (2) Non-Computable

(1) Where there is an algorithm to solve a computer-based problem. e.g. Can we work out if an arbitrary set of patterned tiles can be used to tile a floor?
(2) Where there is not an algorithm that exists that can solve a computer-based problem.

• (1) Decidable & (2) Undecidable

(1) A decision problem that has a Yes/No answer.
(2) A decision problem that is non-computable. e.g. "This statement is false."

• (1) Tractable & (2) Intractable

(1) A problem that has a reasonable (Polynomial) time solution as the size of the inputs increases. e.g. add up a row of numbers.
(2) A problem for which no reasonable (Polynomial) time solution has been found. e.g. Travelling Salesman Problem.

Heuristic Approach
This uses the know-how and experience to make guesses which help solve an intractable algorithmic problem in reasonable (polynomial) time. e.g. 'common sense'

3-1-4 Turing Machine

A Turing machine is an FSM that controls one or more tapes, where at least one tape is of unbounded length (i.e. infinitely long)

Background

• In the early twentieth century, mathematicians were trying to find a universal machine – a mathematical model that consisted of a small number of basic operations and a machine that could perform all these operations.
• The machine would then be able to run any algorithm.
• This model would be a precise definition of the term algorithm. The hope was to find algorithms that would be able to solve all mathematical problems.

 Solvable and unsolvable problems

• Alan Turing was a British Mathematician who, in 1936, wrote a paper called ‘On Computable Numbers’.
• This paper introduced the concept of the Turing machine – a universal machine capable of solving any problem that can be represented algorithmically.
• He used his machine to show that it is not possible to determine if any given problem has a solution, or not. This has serious implications in computing. It means that it may not always be possible to determine if a particular problem is unsolvable, or if it has just not been solved yet.

Turing Machine

• It consisted of:

1. An input alphabet.
2. A tape that is infinitely long.
3. An output alphabet that can be printed on the tape.
4. A tape head that is used to read/write to the cells.
5. A finite set of states, including a start state.
6. A program (set of instructions)

• A Turing machine describes an algorithm.
• A computer uses a computer program that is basically an algorithm.
• Turing machines therefore can be used to run and look at algorithms independent of the architecture of a particular machine.
• An algorithm running on a particular machine will have had to make decisions about how to store values (e.g. the precision of how to store a real number).
• This does not happen on a Turing machine, meaning a Turing machine is a more general representation of the algorithm.

Transition Rules for a Turing Machine

Overview of a Turing Machine

3-1-3 Finite Machines

A Finite State Machine accepts input and processes output.

Examples:

• Traffic Light Control Systems
• Specifiying Computer Language
• Programs for Spell Checking
• Networking Protocols

State Transition Diagrams is used to show a FSM as a picture. Like this:

Finite State Automata (FSA) has a finishing state and only produces yes or no outputs based on the final state.

State 2 is a yes and any other state is a no.

FSM's with outputs:

• Mealy Machine - output on transitions (arrow)

0|A     Input = 0     Output = A

• Moore Machine - output on states (nodes)

C is an output on state 1.

There are two ways to show transitions and states in a FSM.

•  Transition Table - shows transitions and states in table format 



 

• Transition Function - shows transitions and states as a series of functions.

(Input symbol, Current state) -> (Output symbol, Next state)

Deterministic FSA - one and only transition for each input.
Non-Deterministic FSA - multiple transitions for an input.
Halting state - a state with no outputs.
Trigger - input which triggers an action.

3-1-2 Comparing Algorithms

Problems with different time complexities

• Constant Complexity O(1) - takes the same amount of time no matter how big the problem is. (Sort the first ten records in file)
• Linear Complexity O(n) - as the size of the problem increases, the time taken to solve the problem grows at the same rate. (Cutting the grass)
• Logarithmic Complexity O(log n) - as the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time, but a slower rate. (Binary Search)
• Polynomial Complexity O(n^k) - as the size of the problem grows, the time taken to solve it grows faster, but can be solved in a reasonable amount of time. (Shaking hands with everyone in a room)
• Exponential Complexity O(k^n) - as the size of the problem grows, the time taken to solve it grows by larger and larger amounts. Only small size versions of these problems can be solved in a reasonable amount of time. (Emperor's chess board problem)
• Factorial Complexity O(n!) - even worse than exponential, cannot be solved in a reasonable time. (The travelling salesman problem)

Graph of the different time complexities

Key Terms:

Algorithm: a sequence of unambiguous instructions for solving a problem.

Computational complexity of an algorithm: measures how economical the algorithm is with time and space.

Time complexity of an algorithm: indicates how fast an algorithm runs.

Space complexity of an algorithm: indicates how much memory an algorithm needs.

Complexity of a problem: taken to be the worst-case complexity of the most efficient algorithm which solves the problem.

Basic operation: the operation contributing the most to the total running time.

Order of growth: assesses by what factor execution time increases when the size of the input is increased.

Asymptotic behaviour of f: the behaviour of the function f(n) for the very large values of n.

O(g): called big O of g, represents the class of functions that grow no faster than g.

Order of complexity: of a problem is its big O complexity.

3-1-1 Information Hiding and Abstraction

Hiding the design complexity of a system to simplify it for a user.

Levels of Abstraction

1. Application (Word)
2. High Level Programming Language
3. Machine Code
4. Electronics

Examples of Abstraction


• This does not show the actual distance from different stops on the underground.
• It only shows train stops and nothing else, e.g. road maps or landmarks.
• Some stops are not actually a straight line.



















The human brain is an exceptional piece of biological machinery capable of recognising objects when most of their detail has been removed. In this case it is a dachshund (weiner dog).

 
Key Terms

Interface: a boundary between the implementation of a system and the world that uses it. It provides an abstraction of the entity behind the boundary thus separating the methods of eternal communication from internal operation

Abstraction: representation that is arrived by removing unnecessary details.

Information hiding means hiding design details behind a standard interface.

There are several reasons for information hiding. Different objects can have identical interfaces. Sharing a common interface among many different objects means that users of the objects do not need to be retrained when changing from using one object to using another. To use a module or object, a user needs to have no knowledge of its internal design. The internal design can be kept secret. One moudle may be replaced by another module with an identical interface but a different internal design or manner in which the module's function is carried out. Changes are made easier because changes are local to modules.

Find a common representation of a problem, then find an algorithm to solve problems so represented. Learn to transform other problems into this representation.