Sequence 15 — Theory of Computation II

Finite state machines, mathematics for regular expressions, constructing and testing regular expressions, regular languages, BNF grammar and syntax diagrams. AQA 4.4.12–4.4.16.

Finite State Machines: States, Transitions and Tracing

  • Define a finite state machine precisely: states, alphabet, transitions, start state, accepting states
  • Identify states, transitions and accepting states from a specification or diagram
Lesson ready

Constructing and Testing Finite State Machines

  • Construct an FSM from a written specification, defining state meanings before transitions
  • Systematically test an FSM against valid and invalid strings
Lesson ready

Mathematics for Regular Expressions

  • Define alphabet, string, language, concatenation, union and Kleene star precisely
  • Apply these set operations to small example languages
Lesson ready

Constructing and Testing Regular Expressions

  • Construct a regular expression from a written specification
  • Test a regular expression against positive and negative examples
Lesson ready

Regular Languages: Connecting FSMs and Regular Expressions

  • Explain the relationship between a regular language, a regular expression and a finite state machine
  • Construct equivalent FSM and regular-expression representations of the same language
Lesson ready

BNF Grammar and Syntax Diagrams

  • Read a BNF grammar and generate valid strings from it
  • Identify strings that a given grammar does not permit
Lesson ready