ITC562 Theory of Computation (8)

CSU Discipline Area: Computing (COMPU)

Duration: One session

Abstract:

This subject provides the basis for advanced work in theoretical computer science. Finite automata, pushdown automata and Turing machines and their associated languages (regular, context-free and phrase structure languages) are studied. Some practical applications of these abstract machines are covered in the context of language translation. Tools to support language translation are studied.

+ 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: ITC562

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

Enrolment restrictions:

Restricted to students in the Bachelor of Information Technology (Honours) and Bachelor of Computer Science (Games Technology)(Honours).

Objectives:

Upon successful completion of this subject, students should:

* know and be able to understand the mathematical, historical and practical background of the theory of computation;
* be able to understand and prove the capabilities and limitations of the following abstract machines: finite automata, pushdown automata, and Turing machines and their associated languages: regular languages, context-free languages and phrase-structure languages;
* be able to understand the structure of the compilation process of a formal language and understand where the above mentioned abstract machines can be used in this process;
* know how to use tools to assist in the construction of the first stages of a compiler and know the relationship between these tools and the above mentioned abstract machines;
* be able to understand and use recursive function theory and know its relationship to the above mentioned abstract machines;
* know the relationship between symbolic computation and neural networks;
* be able to understand the concept of complexity and analyse the complexity of algorithms;
* know, understand and appreciate some of the philosophical implications of computation theory.

Syllabus:

The subject will cover the following topics:

. Review of function theory. . Review of set theory. . Grammatical basis of language translation. . Historical background of the theory of computation. . Finite state machines and regular languages. . Pushdown automata and context-free languages. . Turing machines and phase-structure languages. . Lexical analysis using the LEX utility. . Parsing using the YACC utility. . Computability and recursive function theory. . Complexity. . Artificial neural networks.

Back