FI:IA052 Topics in Language Theory - Course Information

IA052 Topics in Language Theory

Extent and Intensity

2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: k (colloquium).

Teacher(s)

prof. RNDr. Branislav Rovan, Ph.D. (lecturer), prof. RNDr. Mojmír Křetínský, CSc. (deputy)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Branislav Rovan, Ph.D.

Timetable

each even Tuesday 14:00–17:50 B411

Prerequisites

Knowledge corresponding to courses IB005 (Formal Languages and Automata) and IB107 (Computability and Complexity) is required.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Applied Informatics (programme FI, N-AP)
• Information Technology Security (programme FI, N-IN)
• Bioinformatics (programme FI, N-AP)
• Information Systems (programme FI, N-IN)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Parallel and Distributed Systems (programme FI, N-IN)
• Computer Graphics (programme FI, N-IN)
• Computer Networks and Communication (programme FI, N-IN)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Theoretical Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
• Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
• Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
• Image Processing (programme FI, N-AP)

Course objectives

Main objectives can be summarized as follows: to continue with the subject introduced in the introductory course on formal languages and automata, to introduce selected topic in algebraic theory of formal languages, esp. abstract families of languages and those of automata. Moreover, variants of rewriting systems as extensions of grammars are introduced and discussed.

Syllabus

• Abstract families of languages and automata: definitions of language classes using their closure properties, relationships and dependencies between operations on languages, language family properties implied by automata family properties, operations on automata and their consequences for corresponding languages
• Generalisations of grammars: grammars with controlled derivations, biologically motivated classes of grammars, generative systems, parallel generating languages, complexity of grammars, complexity of languages

Literature

• GINSBURG, Seymour. Algebraic and automata-theoretic properties of formal languages. Amsterdam: North-Holland Publishing Company, 1975, xii, 313. ISBN 0444105867. info
• Handbook of formal languages. Vol. 1 Word, language, grammar. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer, 1997, xvii, 873. ISBN 3-540-60420-0. info
• Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer, 1997, xxii, 528. ISBN 3540614869. info
• Salomaa, A.: Formal Languages. Academic Press, New York, 1973
• Dassow,J., Paun,G.: Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1980

Assessment methods

lectures, optional homeworks. Final written exam (closed books).

Language of instruction

English

Further Comments

The course is taught once in two years.

• Enrolment Statistics (Spring 2009, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring2009/IA052