3-1-6 Regular Expressions, Backus-Neur Form and Reverse Polish Notation

Natural Language:

• Set of words,
• Syntax- rules for putting words together,
• Semantics- meanings.

Formal Language:

• Alphabet.
• Syntax.
• (no Semantics)
  e.g. post codes, number plates

Meta Language:

• Used to express the rules of a formal language.
  e.g. Regular, expressions, Backus-Naur Form

Regular Language:

• One that can be expressed as a Finite State Automata (non-deterministic FSM).

Regular Expression:

• Describes Valid Strings in a Formal Language
  e.g. of a Regular Expression Notation

                                                 a(a|b)* (* = no. of occurrences)
                    (This has to start with an a, and be followed by any number of a's or b's)

                             Valid: a, aa, aabab                                  Invalid: b, ba, abc