Theory of Computation.

What a machine can recognise and what it cannot: automata, grammars, decidability and complexity classes. Covers 10 sub-skills.

• Theory of Computation · 1 of 3

  Context-Free Grammars

  What is a derivation?

  AA sequence of stack pushesBA sequence of input lettersCA sequence of machine states usedDA sequence of rule applications

• Theory of Computation · 2 of 3

  Parsing & Ambiguity

  Do the FIRST and FOLLOW sets detect ambiguity?

  ANo, they only count the rulesBYes, once the table is fullCNo, they only predict a ruleDYes, they flag it directly

• Theory of Computation · 3 of 3

  Regular Expressions Theory

  Which languages have star height zero?

  AAll that a machine acceptsBAll the regular onesCAll the infinite onesDExactly the finite ones