COSC261-15S1 (C) Semester One 2015

Formal Languages and Compilers

15 points

Details:
Start Date: Monday, 23 February 2015
End Date: Sunday, 28 June 2015
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 8 March 2015
  • Without academic penalty (including no fee refund): Sunday, 24 May 2015

Description

This course deals with fundamental concepts and techniques in computer science. It covers automata, formal languages, compilers, computability and complexity theory.

We will cover topics from the following list:
• finite automata and regular expressions
• pushdown automata and context-free grammars
• Turing machines and recursively enumerable languages
• undecidability and the halting problem
• complexity classes and the P=NP problem
• lexical analysis and scanners
• syntactic analysis and parsers
• semantic analysis and optimisation
• code generation

Learning Outcomes

  • After successful completion of this course, students are able to:
  • differentiate formal languages at the various levels of the Chomsky hierarchy,
  • compare the expressiveness of different kinds of automata,
  • apply conversions between languages, automata, regular expressions and grammars,
  • separate undecidable, inefficiently decidable and efficiently decidable problems,
  • use familiar techniques to generate automata and grammars for unfamiliar languages,
  • outline the structure of compilers,
  • analyse the lexical and syntactic structure of programs,
  • use regular expressions and context-free grammars for constructing compilers,
  • produce recursive-descent parsers, and
  • change components of a compiler to deal with new program constructs.

Prerequisites

Restrictions

COSC202, COSC222

Timetable Note

Depending on final student numbers, some of the advertised lab/tutorial streams may not run. Final lab/tutorial options will be available for self-allocation closer to the start of the semester through My Timetable.

Course Coordinator

Walter Guttmann

Lecturer

Kourosh Neshatian

Assessment

Assessment Due Date Percentage 
Quizzes 20%
Assignment Superquiz 10%
Lab Test 10%
Final Exam 60%

Textbooks / Resources

No textbooks are required, but see the following book for additional information:
• Carol Critchlow and David Eck; Foundations of Computation; version 2.3.1, 2011, available here

More advanced or comprehensive books are:
• Michael Sipser; Introduction to the Theory of Computation; third edition, Cengage Learning, 2013
• John Hopcroft, Rajeev Motwani and Jeffrey Ullman; Introduction to Automata Theory, Languages and Computation; Pearson, 2006
• Dexter Kozen; Automata and Computability; Springer, 1997
• Reinhard Wilhelm and Dieter Maurer; Compiler Design; Addison-Wesley, 1995
• Niklaus Wirth; Compiler Construction; Addison-Wesley, 1996
• Alfred Aho, Monica Lam, Ravi Sethi and Jeffrey Ullman; Compilers: Principles, Techniques, and Tools; second edition, Pearson, 2007

Notes

There are several important documents available online about departmental regulations, policies and guidelines at the following site. We expect all students to be familiar with these.

Notices about this class will be posted to the class forum in the Learn system.

COSC students will also be made members of a class called “CSSE Notices”, where general notices will be posted that apply to all classes (such as information about building access or job opportunities).

Additional Course Outline Information

Grade moderation

The Computer Science department's grading policy states that in order to pass a course you must meet two requirements:
1. You must achieve an average grade of at least 50% over all assessment items.
2. You must achieve an average mark of at least 45% on invigilated assessment items.
If you satisfy both these criteria, your grade will be determined by the following University- wide scale for converting marks to grades: an average mark of 50% is sufficient for a C- grade, an average mark of 55% earns a C grade, 60% earns a B- grade and so forth. However if you do not satisfy both the passing criteria you will be given either a D or E grade depending on marks. Marks are sometimes scaled to achieve consistency between courses from year to year.

Aegrotats
If factors beyond your control (such as illness or family bereavement) prevent you from completing some item of course work (including laboratory sessions), or prevent you from giving your best, then you may be eligible for aegrotat, impaired performance consideration or an extension on the assessment. Details of these may be found in the University Calendar. Supporting evidence, such as a medical certificate, is normally required. If in doubt, talk to your lecturer.

Indicative Fees

Domestic fee $778.00

International fee $3,450.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Computer Science and Software Engineering .

All COSC261 Occurrences

  • COSC261-15S1 (C) Semester One 2015