3.1.6 Regular Expressions, Backus-Naur Form and Reverse Polish Notation

1.6 Regular Expressions, Backus-Naur Form and Reverse Polish Notation

Natural Language

Set of Words

Syntax – Rules for putting Words together

Semantics – Meaning

The peanut ate the monkey

                                Syntax – correct

                                Semantics - incorrect

Formal Language

Alphabet

Syntax

(No Semantics)

Examples

                                Post Code

                                Car Number Plates

Meta Languages

These are used to express the rules of a formal language.

Two example of Meta Languages :

                                                Regular Expressions

                                                Backus-Naur Form

Regular Language

Is one that can be expressed as a Finite State Automaton (Non-deterministic Finite State Machine)

Regular Expression

Describes Valid Strings in a Formal Language

Example of Regular Expression Notation

                                                a(a│b)*       

               

                                │ = or      * = Zero or more occurrences

Valid                      a              aa           aabab

Invalid   b             ba           abc

Regular Expression Notation - Basic Symbols

* - Zero or More                                               a*

│ - Or                                                                    a│b

+ - One or More                                                               a+

? – Zero or One                                                 aab?

More Symbols (Meta Characters)

( )   - Brackets

[ ]   - Alternate OR                                            [ab]

-     - Sequence                                  a-z

^    - Not                                                               ^t

\    - Escape Meta Meaning or Shorthand Classes                                               (See Book P.61)

.     - Wildcard Character

Applications

Used in searches for pattern matching…

Eg Google Searches

Backus-Naur Form

It is very difficult to define Programming Languages or Natural Language with regular expressions so we use Backus-Naur Form

Example BNF Definition

Unsigned Integer (this is recursive)

<unsigned integer> ::= <digit>│<digit><unsigned integer>

<digit> ::= 0│1│2│3│4│5│6│7│8│9

Syntax Diagrams

This is another way of defining rules of syntax, in for example a programming language.

<expression> ::= <term> | <term> "+" <expression>

<term> ::= <factor> | <factor> "*" <term>

Reverse Polish Notation

Infix (Normal) is difficult for computers..

4 + 5 x 3                                = 19        Which bit do we do first?

Postfix (RPN) is easy for computers

4 5 +                                       = [in infix]            4 + 5    = 9            

x y – x y + /                         = [in infix]            ( x – y ) / ( x + y )

RPN Removes the need for Brackets

3.1.5- The Halting Problem

Section 1.5: Intractable problems

The Halting Problem

It is not possible to write a program that is able to take any other program and say if that program will halt or not.

When you run a program, it will do one of two things:

        It will run for a while and then halt (stop).

        It will run forever (i.e. it will never halt).

The second of these is not usually a good thing – you would normally want your program to terminate.

Explanation

It is fairly easy to tell that the second program will not terminate as it is a fairly simple program. Most programs are far more complex and you cannot tell by just looking at the code if it will terminate or not.

One way of trying to find out if a program terminates or not is to run the program and see. If the program stops running after a while, you know that the program does terminate. 

The problem with this though is that if the program has not terminated you have no way of knowing if the program does not terminate, or if it has just not terminated yet (if you leave it running for another second it may terminate).

Alan Turing – proof by contradiction

It would be useful if there was a program that could tell you if any program you have written will terminate.

In the 1930s Alan Turing proved that no such program could exist. To show this he used proof by contradiction.

In proof by contradiction you assume that something is true and then show that this results in a contradiction proving it to be false

Example

A program called halt that takes a program as an input and then outputs whether the program can halt or not.

                Halt(program)

                                If program halts then

                                                Return true

                                Else

                                                Return false

The question is whether it is possible to write the program halt? Remembering that it should be able to take any program and say if it halts or not. Therefore, if we find one program that it doesn’t work for then we have proved that it cannot exist.

A new program can be written called contradict which takes a program as a parameter and makes use of halt as a subroutine.

                Contradict(program)

                                If halt(program) returns true then

                                                X = 0

                                                While x<1                           

                                                End while

                                If halt(program) returns False then

                                End

ßif the program reaches the while loop it will get stuck in an infinite loop as x will always be less than 1. If a program enters an infinite loop it doesn’t halt

If when contradict is given itself as a parameter to itself and contradict terminates then halt(contradict) will return true, this means that it will then execute the infinite loop, getting stuck in the process. This is turn means that the program contradict  does not terminate. Which contradicts what was said earlier.

If however contradict does not terminate then halt returns false and the program contradict will then stop running, which means that contradict does terminate which contradicts what was said earlier.

Conclusion

We can now see that if contradict does terminate then it doesn’t. But if it says that it doesn’t then it does.

This isn’t possible and therefore the assumption that it is possible to write the program halt that can take any program and say whether it terminates is false.

It can now be seen that the halting program is uncomputable- it’s not possible to write a program that can tell if any program will halt or not.

3.1.5- Intractable Problems

1.5 Intractable Problems

Types of Problems

We know that some problems can be solved using algorithms and some can’t.

Variety of different types of problem:

•       Algorithmic & Non-Algorithmic,

•       Finite & Infinite,

•       Computable & Non-Computable,

•       Decidable & Undecidable,

•       Tractable & Intractable.

Algorithmic Problems

·         These can be solved using rules or a series of steps.

·         For example; making a cake

Non-Algorithmic Problems

·         These cannot be solved using rules or a series of steps.

·         For example – who would win in a fight between Batman  and Superman?

Algorithmic Problems can be divided into…

FINITE PROBLEMS

•       Finite set of inputs and are SOLVABLE.

INFINITE PROBLEMS

•       Infinite set of inputs and are NOT NECESSARILY SOLVABLE.

Non-Computable Problem

- A problem that has no algorithm to solve it.  Not possible to compute.

More Problem Types

Decision Problems

•       a  Yes/No  Algorithmic Problem

Decidable Problems

•       a Decision Problem that has a Yes/No Answer.

Undecidable Problems

•       a Decision type Algorithmic Problem that is Non-Computable

Example –

‘This Statement is False’

•       This statement is Contradictory therefore it is Undecidable!

Tractable Problems

•       A problem that has a reasonable (Polynomial) time solution as the size of the inputs increases.

•       Example – add up a row of numbers.

Intractable Problems

•       A problem for which no reasonable (Polynomial) time solution has been found.

•       Example – Travelling Salesman Problem.

The Heuristic Approach

The Heuristic Approach uses know-how and experience to make guesses which help solve an Intractable Algorithmic Problem in reasonable (Polynomial) time.

          The ‘Common Sense’  Approach

A variety of different types of problems:

•       Algorithmic & Non-Algorithmic,

•       Finite & Infinite,

•       Computable & Non-Computable,

•       Decidable & Undecidable,

•       Tractable & Intractable.

3.1.4 - Turing Machines

Turing Machines

• Backgroud of the turing machine
• 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
• In 1930, Kurt Gödel showed that there are mathematical statements that it will never be possible to either prove, or disprove.
• Alan Turing then showed that it would not be possible to write an algorithm which could determine if a given mathematical problem (or computer program) was solvable, or unsolvable
• 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.

• How this relates to Computers
• The work done by Turing on mathematical models was the basis from which the first computers were developed.
• It can be shown that anything a modern computer can do can be represented using a Turing machine.

• Turing machine
• A Turing machine consists 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).   

• Another way of looking at this is that a Turing machine consists of a deterministic finite state machine together with an infinitely long tape.

• How this relates to Computers
• 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.

• Universal Turing Machine
• Turing also realised that a Turing machine itself could be encoded and given as an input to another Turing machine.
• This Universal Turing Machine was capable of solving any problem that can be represented as an algorithm.

• Transition Rules
• Transition Rules in a Turing Machine can be represented like this :
•          δ(1,1)=(2,1,→)
• Transition Function(Current State, Input Symbol) = (Next State, Output Symbol, Movement)

3.1.3 Finite State Machines

Finite State Machine (FSM)

• An FSM accepts inputs and processes an output
• Used extensively within computer science applications such as; Traffic light control systems, specifying a computer language, programs fro spell checking, networking protocols
• A state transition diagram is used to show the FSM as a picture

• Finite State Automato (FSA)
• This type of FSM has a finishing state and procedures only a yes/ no output based on the final state. E.g state 2 = Yes.      Other state = No

• FSMs with an output

1. MeaLy machine- Output on the transitions (arrows)
2. MoOre Machine- Output on the states (circles)

1. For example  0|A  The input is 0 while the output is A

  

    2. C is the output for state one, A for state 2 and B for state 3

A FSA which can be programmed easily

•  Transition table
• Shows the states and transitions in an FSM in table format

• Transition Function
• Transition functions show the states and transitions as a series of functions
• (Input Symbol, Current State) (Output Symbol, Next State)

• Deterministic and non- deterministic FSA
• A deterministic FSA has only one transition (arrow) for each input

• A non- deterministic FSA can have multiple transitions for an input. So there is more than one possible route around the state transition diagram

• FSM- Terminology Flash
• Halting state- is a state with no outputs

• Trigger- An input which triggers an output

3.1.2 Comparing Algorithms

Comparing Algorithms
Problems with different time complexities

1) Constant complexities

• O(1)
• Takes the same amount of time no matter how big the problem is.
• E.g. Sorting the first 10 records in a file. Or finding if a number is odd or even.
• IF n mod 2 = 1 THEN odd = true ELSE odd = false
• Can have more than one action

2) Linear complexity

• O(n)
• As the size of the problem increases, the time taken to solve the problem grows at the same rate.
• E.g. Cutting the grass
• Less efficent than O(1) complexity algorithms

3) Logarithmic complexity

• O(log n)
• As the size of the problem grows, the time taken to solve the problem increases, but at a slower rate.
• On sorted lists, there are faster searches than the linear search E.g. Binary search
• Finding an item using the binary search takes on average less time than using the linear search.

4)Polynomial complexity

• O(nk)
• As the size of the problem increases, the time taken to solve it grows faster, but can be solved in a reasonable amount of time
• Includes quadratic and cubic
• Quadratic= O(n^2)
• If a group of people need to shake hands then

                        People            Handshakes needed
                        2                    2
                        3                    3
                        4                    7
                        5                    10
                        6                    15
                        7                    21

• n people need 0.5( n^2 -2) handshakes
• As one increases the other increases more rapidly



http://en.wikipedia.org/wiki/File:Bubble_sort_animation.gif

5) Exponential complexity

• O(kn)
• 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.
• An example is the Emperor's Chess Board Problem

1. The emperor was going to lose his throne to an invading army, he asked for help from a neighbouring war lord.
2. The warlord agreed as long as the pay was good enough. Either 1/4 of China's rice crop for 5 years or the payment via a chess board
3. On the 1st square would be one grain of rice, on the second square 2 grains of rice, on the third square 4 grains of rice and on the 4th 8 grains of rice, etc.
4. The emperor chose the chessboard, and when the invading army was defeated the warlord went to collect his payment. The emperor started putting grains of rice on the chessboard.
5. On the first row there was 225 grains of rice, on the second 65280 grains of rice, on the third 963040.
6. There were several hundred times the amount of rice on the last square on the chessboard alone then there were rice produce by China.
7. The emperor was forced to abdicate.

• This problem although it can be solved, cannot be solved in a reasonable amount of time for anything but the smallest of inputs.

6) Factorial Complexity

• O(n!)
• This complexity is even slower than Exponential Complexity,
• An example of this is the Travelling Salesman Problem
• It cannot be solved in a reasonable amount of time.
• The Travelling Salesman Problem uses the brute forcve method (looks at all routes for the shortest)

            Cities            Possibilities            Time taken to solve
            3                   1                           1 nanosecond
            4                   3                           3 nanosecond
            5                   12                         12 nanosecond
            6                   60                         60 nanosecond
            7                   2520                     0.001814400 seconds
            16                 181440                 11 mins
           

• It is possible to solve the problem in an exponetial way using other methods



Agraph showing the reltionship between the size of a problem and the time taken to solve the problem



   

3.1.1 Information hiding and Abstraction

Information hiding and Abstraction
-Hiding the design complexity of a system to simplify it for a user.
-In Windows the user is unaware of the complexity of a system
-Abstraction- the process of removing unnecessary details. (information hiding) in the representation of a system.
-Reduce the complexity of a system

(Image from http://www.gonative.com/london_tube_map.aspx)

-Levels of Abstraction

1. Application (e.g. Word)- Hides very complex processes behind an icon

2. High level programming language- Hides a number of low level commands behind a high level command.

3. Machine code- Hides the complexity of the underlying electronics behind a machine code command

4. Electronics- Hides the physical processes of atoms and neutons with basic electronic components