 |
|
General Information:
Course syllabus
Course: 2h/week
Lab work: 1h/week = 2h/2weeks
Credit points: 3
Laboratory and Project:
Andrei Vasilateanu, andraevs@gmail.com
Prerequisites:
"Data Structure and Algorithms" and "Object-oriented Programming" courses
Grading and workload
Our grade in the course will be earned / calculated as follows:
- Homework and frequency(c/l/p) 30%+10%
- Final exam 60%
Homeworks will be given roughly every week or two, and will each consist of a small number of exercises. Grades may also be adjusted upward slightly based on regular, positive contributions to class discussions.
Examination Policy
The comprehensive exam consists of a written answer to a quiz and a closed-book, two hours test consisting in analysis, design and implementation of a small application.
Lecture notes: not available
Textbooks:
1. Thomas Sudkamp, Languages and Machines, ed.2, Addison Wesley, 1997.
2. Luca Dan Serbanati, Limbaje si compilatoare, Ed. Academiei, 1987.
3. A.V.Aho, R.Sethi,J.D.Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley, 1986.
|
|
Schedule of Laboratory Topics and Homework
The lab assignments will require knowledge of materials covered by the course lectures.
| Lab.# Week |
Homework Topic |
| Lab. #1
|
Chomsky Grammars. Derivation trees
exercises
|
| Lab. #2
|
Transformations of CFGs
exercises
DFA. Languages accepted by a DFA
exercises
|
| Lab. #3 |
NFA. Languages accepted by a NFA.
NFAs with lambda-transitions.
Equivalence between NFA and DFA
exercises
|
| Lab. #4 |
Regular Expression
exercises
|
| Lab. #5 |
Equivalence between Finite Automata and Regular Expression.Regular Grammar. Pumping Lemma
Recommended readings:
Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages and Computation
pag. 91-105
exercises
|
| Lab. #6 |
Pushdown Automata. Their equivalence with Context-Free Grammars
exercises
|
| Lab. #7 |
Standard Turing Machine. Calculability
exercises
|
|
|
|
|
Lecture Schedule
Please note:
1.This schedule is subject to change
2. Look closely at this site for changes
Date/Time |
Lesson Topic |
Tue, 4 Oct
8h - 12h CJ205 |
Languages. Finite specification of languages. Grammars and Languages. Chomsky's Hierarchy. Derivation Trees in CFGs |
Tue, 11 Oct
8h - 12h CJ205 |
Finite Automata. DFA vs. NFA. DFA Minimizatiation |
Tue, 18 Oct
8h - 12h CJ205 |
Regular sets and expressions. Regular grammars and finite automata
|
Tue, 25 Oct
8h - 12h CJ CJ205 |
Normal forms: Chomsky and Greibach.
|
Tue, 15 Nov
8h - 12h
CJ205 |
Pushdown Automata. Equivalent criteria of acceptance |
Tue, 22 Nov
8h - 12h
CJ205
|
quivalence between Pushdown automata and context-free grammars |
Tue, 29 Nov
8h - 12h
CJ205 |
Turing Machine and Calculability |
Examinations
| Exam Date |
Time/Room |
Fri,13 Jan. |
|
|
|
