Regular languages study guide

1. Start with the language being described

Before writing notation, state what strings or values are allowed. A set lists members explicitly, while set comprehension gives a condition for membership. For example, {0ⁿ1ⁿ | n ≥ 1} is not a list of only the examples shown: the ellipsis indicates that the pattern continues. Each string has a block of 0s followed by an equally sized block of 1s. When examining an answer, check both the order and the equality condition rather than only checking one example.

Distinguish the properties of sets carefully. A finite set has a final element and its cardinality is the number of elements. An infinite set has no final element. A countably infinite set can be counted off by the natural numbers; the natural numbers are an example, whereas the real numbers are infinite but not countable. A Cartesian product is different from a union: X × Y contains ordered pairs formed from one member of each set, so order and pairing matter.

2. Translate a requirement into a regular expression

Break a simple requirement into sequence, choice and repetition. Sequence is written by placing parts next to each other. Use | when there is an alternative, parentheses to group that alternative, * for zero or more repetitions, + for one or more, and ? for an optional part.

For example, a(b|c) represents the two possible strings ab and ac. (ab)+ requires at least one complete ab and can then repeat that block. a(a|b)* requires an initial a, after which any number of a or b symbols may occur. A useful self-check is to test the shortest permitted string, a string using an alternative, and a string using repetition. Also test a tempting but invalid string. If the expression accepts an invalid example, reconsider the grouping or repetition operator.

3. Read and construct FSMs systematically

For an FSM, make a trace table with columns such as input position, input symbol and current state. Begin at the specified starting state, follow one transition for each symbol, and update the state after every symbol. This prevents a common mistake: deciding that a string matches because an intermediate state looks suitable while ignoring the rest of the input. A state transition table and a state transition diagram should describe the same transitions, so compare them row by row or arrow by arrow.

For an FSM with no output, focus on the state reached after processing the input and whether the machine accepts the string. For a Mealy machine, record the output on each transition as well as the next state. Do not move output labels from transitions to states when interpreting a Mealy machine, because that changes the machine being described.

4. Move between equivalent descriptions

Regular expressions and FSMs are equivalent ways of defining a regular language. Given a regular expression, identify states representing progress through its sequence, alternatives and repetitions. Given an FSM, describe the routes that lead to acceptance, combining repeated routes with *, alternatives with |, and groups with parentheses. Keep the language unchanged: the two representations may look different while still describing the same set of strings.

5. Exam self-check

Before finalising an answer, ask: Have I defined the symbols I used? Did I distinguish {} from a set containing an element? Did I use *, + and ? precisely? Did I group alternatives correctly? For an FSM, did I trace every input symbol and account for output if it is a Mealy machine? Finally, test several strings, including the shortest case, an alternative case, a repetition case and an invalid case. These checks expose most errors in simple regular-expression and FSM questions.