← Analysing an area of computer science

Formal languages

Offered in 2 of the last 4 years (2022, 2021), and the richest area for direct application questions — the papers give you a machine, a grammar or a regex and ask you to use it, not just describe it.

The foundations to define precisely

  • A DFA (deterministic finite automaton) is the five-tuple (Q, Σ, δ, q₀, F): Q the finite set of states, Σ the input alphabet, δ the transition function, q₀ the start state, F the accepting states.
  • Deterministic means exactly one transition per state per input symbol — the machine never has a choice, which is what makes it directly implementable.
  • A regular expression matches a pattern using a small, fixed syntax: [a-z] a character range, \d a digit, + one-or-more, * zero-or-more, ? zero-or-one, {3} exactly three, . any character, [^abc] not those characters.
  • A context-free grammar has production rules that rewrite non-terminals (expandable symbols) into terminals (literal symbols) or further non-terminals, starting from a start symbol.
Worked example Tracing a DFA against a string A DFA has states {S1, S2, S3}, accepting state F = {S3}, and transitions: S1 on 'a' → S2, S2 on 'b' → S3, S3 on any symbol → S3, any other transition not shown goes to a non-accepting trap state. Is "ab" accepted? Start at S1 (the start state q₀). Read 'a': S1 → S2 (matches the given transition). Read 'b': S2 → S3 (matches the given transition). No input remains, and the machine is now in S3, which IS in F (the accepting states). ✓ "ab" is accepted — the machine ends in an accepting state after consuming the whole string. This step-by-step trace, ending with an explicit check against F, is what a "which strings does this DFA accept" question is grading.

The capability gap that keeps appearing

  • Regular expressions and DFAs can express repetition and choice, but CANNOT count or match nested structure — they have no memory of how many of something has occurred.
  • A context-free grammar CAN express nesting (balanced brackets, nested expressions) because production rules can call themselves recursively.
  • The classic example: the language "n zeros followed by exactly n ones" cannot be recognised by any finite-state automaton, because doing so would require counting arbitrarily high with only a fixed, finite number of states — but a context-free grammar handles it easily with a self-referencing rule.
✕

"Explain the relative capabilities" needs a NAMED limitation, not a description of each language

A weak answer describes regular expressions, then describes context-free grammars, without ever comparing them. The mark is in stating what one can do that the other CANNOT, and naming the structural reason (a finite-state machine has no memory; a grammar's recursive rules do). "Both are used for parsing" is true but earns nothing without that comparison.

Where formal languages affect people in practice

  • Search and validation: every form field that rejects a badly-formatted email or phone number is a regular expression at work.
  • Programming languages themselves are defined by a context-free grammar, which is why a compiler can tell you exactly where a bracket is unbalanced.
  • Game AI: a finite-state machine is the standard way to give an enemy character a small number of behaviours (patrol, chase, attack) with clear rules for switching between them.

Practise just this