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.