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.