units

FIT2014

Faculty of Information Technology

18 September 2017
01 March 2021

Monash home | About Monash | Faculties | Campuses | Contact Monash |

Staff directory | A-Z index | Site map |

## 6 points, SCA Band 2, 0.125 EFTSLRefer to the specific census and withdrawal dates for the semester(s) in which this unit is offered.
## SynopsisThis 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. ## Objectives
At the completion of this unit, students will have - - 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.
## AssessmentExamination (3 hours): 70%; In-semester assessment: 30% ## Chief examiner(s)## Contact hours2 hrs lectures/wk, 3 hrs laboratory/fortnight, 2 hrs tutorial/fortnight ## Prerequisites
FIT1029 and 6 points of level 1 (or above) mathematics ## Co-requisites6 points of level 1 (or above) mathematics ## ProhibitionsCSE2303 ## Additional information on this unit is available from the faculty at: |