Syntax and Semantics

Organizers: Dr. Radu Mardare
Type - undergraduate course for UCN students
Scheduled for - 2013: 29 Jan , 01 Feb , 05 Feb , 08 Feb , 12 Feb , 15 Feb - from 8:45 AM to 16:00 PM each day
Place: Department of Computer Science, Aalborg University, Selma Lagerlöfs Vej 300, DK-9220 Aalborg, Denmark
Language:
English
ECTS: 5

Lectures:
Lecture 1 -- room 0.1.95
Lecture 2 -- room 0.1.12
Lecture 3 -- room 0.1.12
Lecture 4 -- room 0.1.12
Lectures 5 and 6 -- room 0.1.12
Written Exam -- 18 Feb. 2013, from 9:00 AM to 12:00 AM, room 0.2.90 - see below the examination rules

Description: The course is meant to introduce the basic concepts, methods, results and tools from theoretical computer science. The main focus will be on the Theory of Computation, Automata Theory and Structural Operational Semantics. With some of these methods, the students are already familiar from their practical experience in Computer Science. The course will stress on the theoretical, mathematical and logical aspects. The course will consist in lectures and exercise sessions. There will be a major emphasize on solving theoretical problems. After attending this course, the students should be able to use the basic theoretical concepts from computer science and apply them in organizing their projects.

Prerequisites: No particular background is expected from a student that is attending this course. However, being the structure of the course, the students are expected to study intensively during the teaching period; the presence at the lectures and at the exercise sessions as well as preparing the homeworks are mandatory.

Formally, the course will cover the following topics:

I. Automata and Languages
I.1. Regular Languages
I.1.1. Finite Automata
I.1.2. Nondeterminism
I.1.3. Regular Expressions
I.1.4. Nonregular Languages
I.2. Context-Free Languages
I.2.1. Context-Free Grammars
I.2.2. Pushdown Automata
I.2.3. Non-context-free Languages

II. Semantics
II.1. Basic principles of Semantics
II.1.1 Abstract Syntax
II.1.2. Transition Systems
II.1.3. Big-step versus Small-step semantics
II.1.4. Elements of Operational Semantics
II.2. Language Constructs
II.2.1. Control structures
II.2.2. Blocks and Procedures
II.2.3. Parameters

Bibliography
Part 1: Automata Theory
[1] Michael Sipser, Introduction to the Theory of Computation
[2] J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages and Computation
[3] A. K. Dewdney, The New Turing Omnibus
Part II: Semantics
[3] Hans Huttel, Transition and Trees
[4] H. R. Nielson, F. Nielson, Semantics with Applications

Examination Rules: The final examination consists in evaluating:
1. The activities of group-solving problems - the students are evaluated for their contribution during the lectures at the common problem solving activities and discussions.
2. The homeworks assignments - the deadline for presenting the homeworks is 18 Feb. 2013, 9:00 AM
3. The written examination that will take place on 18 Feb. 2013, from 9:00 AM to 12:00 AM, room 0.2.90
To pass the exam, a student has to obtain the qualification "pass" to each of the activities 1, 2 and 3.