Regular languages revision notes

Regular languages

A language is called regular if it can be represented by a regular expression. Equivalently, a regular language is any language that a finite state machine (FSM) will accept. Regular expressions and FSMs are therefore two equivalent ways of defining a regular language.

Sets used to describe languages

A set is an unordered collection of values in which each value occurs at most once. For example, A = {1, 2, 3, 4, 5}. Set comprehension gives a rule for membership, such as A = {x | x ∈ ℕ ∧ x ≥ 1}. Here, | means “such that”, ∈ means “is a member of”, and ∧ means AND. The natural numbers are ℕ = {0, 1, 2, 3, ...}. The empty set has no elements and can be written {} or Ø.

A compact language description such as {0ⁿ1ⁿ | n ≥ 1} represents strings containing some number of 0s followed by the same number of 1s: {01, 0011, 000111, ...}. A finite set has a final element, whereas an infinite set does not. A countably infinite set can be counted off by the natural numbers. The cardinality of a finite set is its number of elements. The Cartesian product X × Y is the set of all ordered pairs (a, b) where a ∈ X and b ∈ Y.

A subset contains no elements outside another set. ⊆ includes equality, so {0, 1, 2, 3} ⊆ {0, 1, 2, 3} is true. A proper subset, written ⊂, must be smaller: {0, 1, 2} ⊂ ℕ. Set operations include membership, union, intersection and difference. The difference A\\B contains elements in A that are not in B.

Regular expressions

A regular expression is a shorthand way of describing a set of strings. The expression a(a|b)* generates strings beginning with a, followed by zero or more as or bs. Examples include a, aa, ab, aaa, aab and aba.

Important metacharacters are:

• *: zero or more repetitions.
• +: one or more repetitions.
• ?: zero or one repetition, so the item is optional.
• |: alternation, meaning OR.
• ( ): grouping.

For example, a(b|c) matches ab or ac; (ab)+ describes one or more repetitions of ab; and a?b describes b or ab. Parentheses determine which part an operator applies to.

FSMs

An FSM can be represented by a state transition diagram or a state transition table. An FSM with no output describes how input symbols cause transitions between states. An FSM with output produces output as it processes input; for this specification, the output form is a Mealy machine. In a Mealy machine, the output is associated with a transition, rather than being treated as a separate output attached only to a state.

To interpret an FSM, follow the transition for each input symbol in order and record the resulting state or output. To construct one, identify the required states, label transitions with the relevant input symbols, and show the transitions clearly. To construct an equivalent regular expression, describe exactly the strings whose processing follows an accepting route. To construct an FSM from a regular expression, create states that represent the required progress through the pattern, including alternatives and repetition.

Common errors

Do not confuse * with +: * permits zero repetitions, while + requires at least one. Do not treat | as part of the literal string when it means alternation. Do not assume that a set is ordered or that repeated values are stored more than once. Check whether a subset is proper, because ⊂ excludes equality whereas ⊆ permits it. When reading an FSM, process every input symbol in sequence and do not skip a transition.