Regular languages exam tips

Exam tips

• Trace one input at a time

  For a sequence, write the current state, the input, the transition taken, the output if there is one, and the resulting state at every step.

  This makes it clear that each input uses the state reached by the previous input and helps avoid missing or reordering outputs.

• Translate notation before calculating

  When given set-builder or compact notation, identify the condition on each element before listing or manipulating the set.

  This helps distinguish symbols such as ∈, ∧ and |, and reduces errors when interpreting restrictions such as n ≥ 1.

• Break the expression into sections

  When checking a string, identify the required beginning, ending, alternatives and repeated parts separately.

  This makes it easier to verify whether every part of the regular expression has been satisfied and reduces errors with *, +, ? and |.

• Give both definitions

  When asked to define a regular language, mention both regular expressions and FSM acceptance where appropriate.

  This demonstrates knowledge of the two equivalent descriptions stated in the specification.