Regular & Context Free Languages

• A finite state machine is a model of computation. We can represent them via state transition diagrams
• A finite state machine has a number of states, of which it can only be in one at any given time. These are represented as circles.
• A finite state machine needs a start state, represented by an arrow coming in from nowhere pointed at the start state
• Transition arrows connect different states together, and allow us to move from one state to another
• Each transition arrow needs a transition condition - the condition or input that causes a change of state
• A finite state machine might have a stop state, indicated by a double circle
• A Mealy machine is a finite state machine with output
• A Mealy machine's output is determined by both the input and the current state it is in
• A set is an unordered collection of values where each value only appears once
• An empty set can be represented as {} or Ø
• Sets can contain other sets
• A finite set contains a finite amount of numbers that can be counted using natural numbers
• Cardinality refers to the number of elements in a finite set
• An infinite set has no end value - they contain an infinite number of elements, for example natural numbers (ℕ) or real numbers (ℝ)
• A countably infinite set is a set that can be counted off against natural numbers. ℕ is a countably infinite set, but ℝ is not.
• Set comprehension is a way of specifying a set that may look like this:

  A = {x | x ∈ ℕ ∧ x ≥ 1 }
• A = {} means 'The set "A"'
• | means 'such that'
• ∈ means 'belongs to'
• ∧ means 'and'
• A = {x | x ∈ ℕ ∧ x ≥ 1 } reads "The set 'A' equals x, such that x belongs to the set of natural numbers and x is greater than or equal to 1"

  In other words, A = {1, 2, 3, 4...}
• The cartesian product of two sets is the set of ordered pairs (a,b), written as A x B (A cross B)
• If A = {w, x} and B = {y, z}

  A x B = { (w, y), (w, z), (x, y), (x, z) } (this is the cartesian product)
• Compact set representation uses shorthand to describe multiple instances of a number. For example, {0n1n | n ≥ 1} means a set of all numbers with an equal amount of 0s followed by 1s
• Set A is a subset of set B if A only contains elements present in B, written as A ⊆ B. This includes if A is exactly the same as B
• Set A is a proper subset of set B if A only contains elements present in B, but not all of them, written as A ⊂ B
• A countable set is any set where the cardinality is the same as a subset of natural numbers
• We can add two sets together to create a new set - this is called union, written as A∪B
• The intersection of two sets is all elements that both sets have in common, written as A∩B
• A set difference is a set created from items exclusive to one set, written as A\B or A-B
• Everything which is in set A but not in set B:

  A\B = {x : x ∈ A and x ∉ B}

  x, where x is a member of set A and is not a member of set B
• ∈ denotes membership - whether or not an item is in a set
• A regular expression is a way of describing a set, which allows computers to work with text patterns
• A regular expression can specify strings that meet a given condition
• Regular expressions use special symbols called metacharacters
• * means zero or more preceding elements
• + means one or more preceding elements
• ? means zero or one preceding elements (the previous element is optional)
• Regular expressions and finite state machines are equivalent
• A language is regular if it can be represented by a regular expression