ITC361 Computational Models (8)

CSU Discipline Area: Computing (COMPU)

Duration: One session

Abstract:

The theory part of the subject introduces the student to the theoretical bases of computation, including the theory of parsing and complexity. The practical component of the subject serves to acquaint the student with the development of lexical analysers and parsers. This provides a basis for any study of compiler construction.

+ Subject Availability Modes and Locations

No offerings have been identified for this subject in 2013.Continuing students should consult the SAL for current offering details prior to contacting their course coordinator: ITC361

Where differences exist between the handbook and the SAL, the SAL should be taken as containing the correct subject offering details.

Assumed Knowledge:

MTH129 and (ITC106 or ITC129 or ITC140 )

Objectives:

Upon successful completion of this subject, students should:

* be able to describe the various types of abstract computational machines and the languages they recognise;
* be able to describe the role of lexical analysis and parsing in the design and implementation of compilers;
* be able to describe the fundamentals of computability theory;
* be able to describe the fundamentals of complexity theory.

Syllabus:

The subject will cover the following topics:

. Introduction to Set Theory . Deterministic and non deterministic finite automata . Regular grammars, expressions and languages . Pushdown automata . Context-free grammars and languages . LL(k) and LR(k) parsers . Turing Machines . Phrase-structure grammars and languages . Computability including recursive function theory, primitive recursive functions and partial recursive functions . Time and space complexity of computations, algorithms and problems . Lex and Yacc Unix utilities for lexical analysis and parsing

Back