[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]

Associate Professor David Dowe
Associate Professor
Phone: +61 3 990 55776
Fax: +61 3 990 55157

Lecturer(s) / Leader(s):

Clayton

Associate Professor David Dowe
Associate Professor
Phone: +61 3 990 55776
Fax: +61 3 990 55157

Malaysia

Mr Kar Loke

Introduction

Welcome to FIT2014 Theory of Computation.

The following guide is given so that you can have a productive semester and you can complete the unit successfully.

Unit synopsis

This unit looks at the question of exactly what a computer can compute, and gives an introduction to formal languages. Topics include computable functions, finite state automata, regular expressions, grammars, translators, and Turing computability.

Learning outcomes

At the completion of this unit, students will have an understanding of:
  1. How to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Mealy Machines, Moore Machines, Context Free Grammars, Pushdown Automata, and Turing Machines.;
  2. The relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
  3. How to use Turing Machines to represent computable functions;
  4. How a Universal Turing machine can simulate any Turing Machine on any input;
  5. Knowledge of compiler generation tools and the ability to use these to create simple compilation/translation programs.

At the completion of this unit, students will have attitudes that will allow them to:
  1. Appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
  2. Comprehend the limitations of computers in terms of the problems they can solve.

At the completion of this unit, students will be able to:
  1. Construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
  2. Use Finite Automata to construct lexical analysers;
  3. Use lexical analyser generator to construct lexical analysers;
  4. Convert Regular Expressions into a Finite Automata;
  5. Convert Finite Automata into Regular Expressions;
  6. Use a compiler complier to construct parsers;
  7. Find a Regular Grammar for a Regular Language;
  8. Find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
  9. Know how to show a Context Free Grammar is ambiguous;
  10. Convert Mealy Machines and Moore Machines into sequential logic circuits.

Contact hours

8 x contact hrs/fortnight

Workload

Average of 12 hours per week: 2 hours lecture (each week), either 1 hour tutorial or 3 hour laboratory (alternating weeks), and 8 hours of reading, working on exercises and assignment(s), etc.

Unit relationships

Prerequisites

FIT1008 or FIT1015 (CSE1303) and 12 points (or 6 points completed and 6 points enrolled) from MAT1830, MAT1841, MTH1020, MTH1030, MTH1112, MTH2010.

Prohibitions

CSE2303, CSC2030

Relationships

This is a second year core unit in BCS, BSE, BCS/BA, BCS/LLB, and BSc/BCS, and is a second year core unit in a computer science major in BSc. It introduces students to the formal theory of languages, lexical analysers, compilers, and the limitations of what computers can compute.

Teaching and learning method

You are expected to read through the prac notes before each prac class, and you are expected to have performed the preparatory tasks described in the notes before the start of each prac. Please ask your lecturer before your prac if you do not understand the requirements for the prac.

Most prac work is designed so that most students cannot start and finish it in three hours. You must devote considerable thought to the prac work prior to attending the prac, and (ideally or) realistically you should have code already written for a substantial portion of the prac prior to attending it. The prac session itself should be used to seek assistance with respect to unresolved issues, to finalize programs, and to de-bug and test your programs.

If you have trouble preparing for the prac you should seek assistance concerning requirements and approaches to the problem from tutors or lecturers during consultation hours.

Timetable information

For information on timetabling for on-campus classes please refer to MUTTS, http://mutts.monash.edu.au/MUTTS/

Tutorial allocation

On-campus students should register for tutorials/laboratories using the Allocate+ system: http://allocate.cc.monash.edu.au/

Unit Schedule

Week Topic References/Readings Key dates
1 Regular Languages Cohen: Chapters 1-4  
2 Finite Automaton Cohen: Chapters 5-7  
3 Lexical Analysis Aho et al.: Chapter 3  
4 Kleene's Theorem Cohen: Chapters 7,8  
5 Context Free Grammars Cohen: Chapters 10, 12  
6 Parsing Aho et al.: Sections 4.2 & 4.3  
7 Rewriting Grammars Aho et al.: Chapter 1  
8 Predictive Parser Aho et al.: Section 4.4  
9 Compiler-Compilers Aho et al.: Section 4.4  
10 Turing Machines Cohen: Chapters 13-16,19  
Mid semester break
11 Computability Cohen: Chapters 23,25  
12 Decidability Cohen: Chapter 23  
13 Godel Incompleteness Theorem    

Unit Resources

Prescribed text(s) and readings

Daniel I. A. Cohen, "Introduction to Computer Theory", Second Edition, John Wiley & Sons, Inc. 1997.

Recommended text(s) and readings

Michael Sipser, "Introduction to the Theory of Computation", PWS Publishing Company, 1997

A.V. Aho, M. S. Lam, R. Sethi and J. D. Ullman. "Compilers: Principles, Techniques and Tools", 2nd edition, Addison-Wesley, 2007.

Required software and/or hardware

You will need access to:

  • Cup available via: http://www2.cs.tum.edu/projects/cup/
  • Jflex available via: http://jflex.de/

Study resources

Study resources we will provide for your study are:

  • Weekly detailed lecture notes;
  • Tutorial exercises and laboratory tasks;
  • Tutorial solutions (approx.) two weeks later; 
  • Access to at least one sample examination paper or past examination paper;
  • Discussion groups;
  • This Unit Guide outlining the administrative information for the unit;
  • The unit web site on MUSO/Blackboard, where resources outlined above will be made available.

Assessment

Overview

Compulsory assessed laboratory classes: 30%; Examination: 70%.

Faculty assessment policy

To pass a unit which includes an examination as part of the assessment a student must obtain:

  • 40% or more in the unit's examination, and
  • 40% or more in the unit's total non-examination assessment, and
  • an overall unit mark of 50% or more.

If a student does not achieve 40% or more in the unit examination or the unit non-examination total assessment, and the total mark for the unit is greater than 44% then a mark of no greater than 44-N will be recorded for the unit.

In order to pass this unit you must:

  • Obtain at least 50% on the exam.
  • Obtain at least 50% overall for your pracs.
  • Attend four out of the five pracs this semester.
  • Obtain an overall mark of at least 50%.

If you do not meet all of the above conditions the highest mark you can receive is 44N.

Students should also be familiar with the consequences of plagiarism, for the students who copy and also to any (other) students who allow their work to be copied.  The best possible outcome for students in such an event is zero marks for the relevant question(s) and an official letter sent to them and kept on their file.  But students should also understand that is the best possible outcome, and other possible outcomes include zero marks for the entire assignment or even zero marks for the entire subject.  As a general  rule, penalties tend to be more severe for repeat offenders.

Assignment tasks

Assignment coversheets

Assignment coversheets are available via "Student Forms" on the Faculty website: http://www.infotech.monash.edu.au/resources/student/forms/
You MUST submit a completed coversheet with all assignments, ensuring that the plagiarism declaration section is signed.

Assignment submission and return procedures, and assessment criteria will be specified with each assignment.

  • Assignment task 1
    Title:
    Pracs (3 hours)
    Description:
    Each week (weeks 4, 6, 8, 10 and 12) you will need to complete a prac assignment. Prac assignments are long and are designed to take a significant part of your ``home study hours''. This means that you must have a significant proportion of the prac completed before attending the scheduled computer lab. The aim of the computer lab practical is to iron out any bugs, ask any questions about the prac you have not been able to solve on your own, improve the parts that your demonstrator points out as lacking (including comments, algorithms, etc), and get your prac marked. If you do nothing before the scheduled prac, you will soon realise that you do not have enough time to complete it.  The prac sheets will be released approx. every Thursday morning and made available in the unit's web page.

    Unless explicitly specified otherwise by both your lecturer and your prac' demonstrator, your assignment work is to be done from your Monash student account and demonstrated on one of the Monash computers in your scheduled Monash lab.

    The form(s) of your assignment submission - identical soft electronic and/or hard copies - will be elaborated upon in the assignment statement.  Your assignment will be deemed submitted when all of these versions are submitted.
    Weighting:
    30%
    Due date:
    Remarks:
    There are two hurdles associated to the pracs. First, you must attend at least 4 out of the 5 pracs. Second, you must score at least 50% of the prac mark. A student who does not meet all these hurdles can get a maximum of 44 N for the unit.

Examination

  • Weighting: 70%
    Length: 3 hours
    Type (open/closed book): Closed book
    Remarks:

    There is a hurdle associated with the exam mark: you must score at least 50% of the exam mark. Furthermore, you must score at least 50% overall.

See Appendix for End of semester special consideration / deferred exams process.

Due dates and extensions

Please make every effort to submit work by the due dates. It is your responsibility to structure your study program around assignment deadlines, family, work and other commitments. Factors such as normal work pressures, vacations, etc. are not regarded as appropriate reasons for granting extensions. Students are advised to NOT assume that granting of an extension is a matter of course.

Students requesting an extension for any assessment during semester (eg. Assignments, tests or presentations) are required to submit a Special Consideration application form (in-semester exam/assessment task), along with original copies of supporting documentation, directly to their lecturer within two working days before the assessment submission deadline. Lecturers will provide specific outcomes directly to students via email within 2 working days. The lecturer reserves the right to refuse late applications.

A copy of the email or other written communication of an extension must be attached to the assignment submission.

Refer to the Faculty Special consideration webpage or further details and to access application forms: http://www.infotech.monash.edu.au/resources/student/equity/special-consideration.html

Late assignment

If you miss a prac or tutorial class for any reason you must do the following to obtain an exemption for the missed class:

  • Submit an absentee form no more than one week after you return to University. These forms are available from and should be handed in to the General office (Clayton) in building 63 (Ground floor).
  • Attach any documentary evidence - for example, medical certificate or police statement, letter of explanation, police report or plane boarding pass, etc. - covering the date of your missed class.

Failure to do the above will result in you being marked absent for the class and receiving zero marks. Exemptions will not be granted automatically, and will be considered on a case by case basis. You are also only allowed one exemption a semester for this unit.

Assignments received after the due date without adequate medical or other reason will be subject to a penalty of up to 5% per day, including weekends. An assignment is deemed late if any of the submitted versions (recall ``Assessment details'', ``Assignment submission'') is late.  Assignments received later than one week (seven days) after the due date will not normally be accepted. In some cases, this period may be shorter if there is a need to release sample solutions or discuss solutions in class.

Where multiple versions of an assignment are to be submitted (e.g., soft electronic copy on MUSO/Blackboard and/or Damocles, and hard copy to the General Office), versions must be identical and the time of submission will be deemed to be when the final version is submitted and received.

This policy will often be strictly adhered to because comments or guidance will be given on assignments as they are returned, and sample solutions may also be published and distributed - after assignment marking or with the returned assignment.

Return dates

Students can expect assignments to be returned within two weeks of the submission date or after receipt, whichever is later.

Appendix

Please visit the following URL: http://www.infotech.monash.edu.au/units/appendix.html for further information about:

  • Continuous improvement
  • Unit evaluations
  • Communication, participation and feedback
  • Library access
  • Monash University Studies Online (MUSO)
  • Plagiarism, cheating and collusion
  • Register of counselling about plagiarism
  • Non-discriminatory language
  • Students with disability
  • End of semester special consideration / deferred exams
[an error occurred while processing this directive]