This is NOT the current version of the course; please visit here for Fall 2016

Short description: The course is an introduction to two foundational concepts in cognitive science: structural representations and computation. As empirical domain, we look at increasingly complex structural representations from morphology and syntax of natural languages. We couple this with an introduction to the theory of computation. We aim to establish that (i) human language capacity is (based on) a computationally describable unconscious system of rules and representations; (ii) that there are mathematically precise ways of talking about different types of structural relations; and (iii) that bringing these two together opens up new avenues in the cognitive scientific investigation of language.

Instructor: Umut Özge, umozge@metu.edu.tr
Room B-208, phone: 210 7884, 0530 142 6850
Office hours are by appointment - call or drop an email.

Teaching assistant: Ece K. Takmaz, etakmaz@metu.edu.tr

News and discussion: in class and the Google group of the course.

Time and place: Tuesdays, 9:00-11:50, II-03 (No class on Nov 10th, last class on Jan 5, 2016).

Outline of the course:

• General introduction
• Morphology (1.5 weeks)
• Regular languages and finite automata (2 weeks)
• Morphology and computation (1 week)
• Syntax (2 weeks)
• Context-free languages and push-down automata (2 weeks)
• Syntax and computation (2 weeks)
• Languages beyond context-free, Turing Machines

Material:

Lecture notes:

Notes will be available in hard copy at the start of each class, and will be posted on the website afterwards.

• General introduction
• Morphology
• Regular languages
• Finite automata
• Syntax
• Context-free grammars and languages
• ...

Homeworks and exercises:

hw1 on morphology
hw2 on basics of formal languages,regular languages,	hw2-solutions
hw3 on fa and regular expressions
hw4 on morphology and fa	hw4-solutions
hw5 on syntactic constituency	hw5-solutions
hw6 on cfg's	hw6-solutions
hw7 on cfg's and pumping lemma for fal's

A study check-list for the final exam.

Reference:

Tallerman, M. (2011). Understanding Syntax. Hodder Education, Croydon, UK.
Payne, T. (2006). Exploring Language Structure: A Student's Guide. Cambridge University Press.
Sudkamp, T. A. (1997). Languages and Machines: An Introduction to the Theory of Computer Science. Addison-Wesley, Reading, MA, 2nd edition edition.
Partee, B. H., ter Meulen, A., and Wall, R. E. (1990). Mathematical Methods in Linguistics. Kluwer, Dodrecht.

Resources:

Some graph visualization tools for drawing finite automata:

Graphviz
Qfsm
Finite state machine designer

Requirements: There will be a homework every two weeks (70%); and a final exam (30%) at the end of the term, all based on what we have seen in class, the readings and homeworks (!). 75% attendance is required; you must not miss more than three classes to be eligible to pass the course.

---