Course Title : Formal Languages and Computation Theory
Course Number: COT 6315 (CM710-R NTU)
Section	     : 7333
Credits      : 3

Objectives : A study of the formal relationships between machines,
	languages and grammars; we will cover regular, context-free,
	context-sensitive, recursive and recursive enumerable languages 
	along with undecidability and intractability.

Prerequisites : Discrete mathematics (elementary graph theory, elementary 
	set theory, proof techniques), data structures.

Grading :
	Examinations					75%
	Homeworks and class participation 		25%

Textbook (required):
	Sipser, Introduction to the Theory of Computing, 
		PSW Kent, Boston, MA, 1997.  ISBN 0-534-94728-X

Reference Books (not required) :
	Hopcroft, Motwani and Ullman, Introduction to Automata Theory, 
		Languages, and Computation 2/e, Addison-Wesley, Reading, MA
		2001.  ISBN 0-21002988-X
	Martin, Introduction to the Theory of Language and Computation,
		McGraw-Hill, ISBN 0-07040659-6

Course Outline Topics :
	Introduction - Basics and Motivation
	Regular Languages, Regular Grammars, Finite Automata
	Context-Free Languages, Context-Free Grammars, Pushdown Automata
	EXAM 1 (25%)
	Turing Machines, Recursive Languages, r. e. Languages
	Undecidability
	EXAM 2 (25%)
	Introduction to Complexity Theory
	Space Complexity
	Intractability
	EXAM 3 (25%)

Professor    : R. E. Newman (nemo@cise.ufl.edu)
Office       : CSE 346 (352) 392-1488
URL          : http://www.cise.ufl.edu/~nemo/cot6315/
Office Hours : T, R 2:00-3:30

TA	     : Arslan, Bekir (barslan@cise.ufl.edu)
Office	     : tbd
Office Hours : tbd

Class Room : CSE 107 (FEEDS Studio A)
Class Hours : T 2-3 (8:30-10:25), R 3 (9:35-10:25)

Homework Policy:  Homeworks will be collected at the start of the class
	on which the homework is due.  Sample questions from the homework
	will be graded, the rest are assigned for you to consolidate and to
	apply what you have read or heard.  There will be about one homework
	per week, and occasional bonus problems.
	Late homeworks will be accepted up until the start of the class in
	which the homework answers are reviewed.  Each class day the homework
	is late will result in a 10% deduction in the grade.

Bonus Problems:  Bonus problems are not required, but if you submit them and
	do well, then when final grading is done they may help you if you
	are "on the bubble" between letter grades.

Examinations:  There will be three midterms and no final.  All will be closed
	book, closed notes.  You are permitted one 8.5" x 11" crib sheet
	(two-sided) containing notes of your chosing for each exam.

Collaboration Policy:
	You are encouraged to discuss the course and the homework assignments 
	with each other after you have attempted the problems yourself.  
	However, your exams should be your own work.

Comment:  This is going to be a fast-paced course covering a great deal in
	a short time.  Please be diligent in staying ahead of the assignments
	since you are likely to find it difficult to catch up if you get
	behind.  You should read the book section(s) to be covered ahead of
	class and make note of any points you find difficult.  If the lecture
	does not make these clear, please ask about them in class, or during
	office hours.  Homework problems should be attempted no later than
	the day in which the material is covered in class.  If you receive
	substantial help on a problem (e.g., a written answer from *any*
	source), you should indicate the source with your answer, along with
	a clear indication of what you contributed and what was from the
	source.  Failure to do this constitutes plagiarism.