This unit gives an introduction to formal languages using logic programming and looks at what a computer can compute and what problems are intractable. Examples include why it is so difficult to design timetables, get computers to play Go, or crack a code. Topics include computable functions, finite state automata, regular expressions, grammars, Turing computability, polynomial-time reductions, and NP-completeness.
At the completion of this unit, students will have -
A knowledge and understanding of:
- propositional and predicate logic;
- how to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Context Free Grammars, Pushdown Automata, and Turing Machines;
- the relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
- how to use Turing Machines to represent computable functions;
- how a Universal Turing machine can simulate any Turing Machine on any input;
- basic computational complexity theory, including verifiers, polynomial-time reductions and NP-completeness.
Developed attitudes that will allow them to:
- appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
- comprehend the limitations of computers in terms of the problems they can solve;
- appreciate that there are many solvable problems which cannot be solved in polynomial time.
Developed the skills to:
- use propositional logic to represent and analysis problems in the theory of computation;
- construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
- convert Regular Expressions into a Finite Automata;
- convert Finite Automata into Regular Expressions;
- find a Regular Grammar for a Regular Language;
- find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
- know how to show a Context Free Grammar is ambiguous;
- show a problem is NP-complete.
Examination (3 hours): 70%; In-semester assessment: 30%
Minimum total expected workload equals 12 hours per week comprising:
(a.) Contact hours for on-campus students:
- Two 1-hour lectures
- Either one 1-hour tutorial or one 3-hour laboratory (alternating weeks)
(b.) Additional requirements (all students):
- A minimum of 8 hours of independent study per week for reading, working on exercises and assignment(s).
FIT1029 and 6 points of level 1 (or above) mathematics