Below is the outline of the outcomes of the subject. After reviewing the past exam papers it seems like each chapter is well represented in the exam and so it would be best to have an understanding of all the outcomes.
Chapter 2 – Languages
What an alphabet, a word, a language and the empty string are; what is meant by the length of a string; how to concatenate strings; what the closure of a set is, and how to form it; what Cohen means when he speaks of ‘proof by constructive algorithm’; Chapter 3 – Recursive definitions
use of recursion; formulate proofs by induction; Chapter 4 – Regular Expressions
recognise whether an expression is regular; describe the language associated with a given regular expression; write down the regular expression that defines a given language; prove that any finite language is defined by a regular expression; Chapter 5 – Finite Automata
check whether something is a finite automation; test whether a given word is accepted by a given finite automaton; design a finite automaton to recognise a given language; describe the language accepted by a given finite automaton; Chapter 6 – Transition Graphs
check whether something is a transition graph; test whether a given string is accepted by a given transition graph; design a transition graph to accept a given language; explain what non-determinism is; Chapter 7 – Kleene’s Theorem
sketch the proof of Kleene’s theorem; apply the algorithms used in the proof to build FA’s or regular expressions; define a non deterministic automaton (NFA); describe the language accepted by a given NFA; design a FA that is equivalent to a given NFA; prove that FA = NFA Chapter 8 – Finite Automata with output
define a Moore machine; define a Mealy machine; prove that Me = Mo; design a Me that is equivalent to a given Mo; design a Mo that is equivalent to a given Me; design a Me o a Mo for a given sequential circuit; Chapter 9 – Regular Languages
show that the set of regular languages is closed under the operations of union, concatenation, closure, complementation and intersection; find for given regular languages L1 and L2, a regular expression and an FA defining L1 Union L2 Chapter 10 – Non-regular Languages
give examples of non-regular languages; prove the pumping lemma without length and the pumping lemma with length (Theorem 13 & 14); apply the pumping lemma with length and the pumping lemma without length to show that language is non-regular; Chapter 11 – Decidability
define the notions of ‘decision procedure’ and ‘decidable problem’; determine whether two FA’s accept the same language or not; determine whether a given FA accepts any string at all; determine whether a given FA accepts a finite or an infinite language;
