|University: Technical University of Košice|
|Faculty: Faculty of Electrical Engineering and Informatics|
|Department: Department of Computers and Informatics
|Course Number: 26000634||Course Name: Formal Languages|
|Type, scope and method of learning activities:
Course Type: Lecture, Laboratory exercise
Recommended scope of the course content (in hours):
Full-time study (hours per week): 3,2
Part-time study (hours per semester): 39,26
|Number of credits: 6|
|Recommended semester of study: ST|
|Recommended semester||Study programme||Study grade||Study Method|
|2.rok ST||Informatics (INF_Bc_D_sk)
|Level of study:|
|Course completion requirements:
Assessment and completion of the course: Credit test and examination
Continuous assessment: Student passes the continuous assessment and receives credits when he or she meets the requirement to obtain at least 16% out of 30%.
Final assessment: Student passes the final assessment and passes the examination when he or she meets the requirement to obtain at least 36% out of 70%.
final test, exam
Overall assessment: Overall assessment is the sum of the assessments obtained by students in the assessment period. The overall result is determined in accordance with the internal regulations of the Technical University in Košice. (Study Regulations, the internal regulation principles of doctoral studies)
Subject is dedicated algorithms and techniques for processing strings, especially parsing and processing sentences formal languages. After completing the course the student should know how to use regular expressions and understand the definition of formal languages using grammars. It should be able to design and implement a grammar parser simple context-free language. Moreover, it should know the basic algorithms for finding patterns in strings and text.
|Brief course content:
1. Strings and formal languages, regular expressions, regular languages and their application.
2. The relationship of regular expressions and finite state automata.
3. Grammars and context-free languages, syntactic analysis, parser generators.
4. Lexical analysis, implementation of recursive parser.
5. The structure of language and the language processor, design principles of languages.
6. Relationship of context-free languages and pushdown automata, Chomsky hierarchy of languages.
7. Top down syntax analysis.
8. Bottom up syntax analysis.
9. Syntactic errors and error recovery.
10. Algorithms and data structures for search strings and text patterns.
11. Algorithms for string comparison.
12. String representation in computer text encoding.
|Recommended Reference Sources:
1. John E. Hopcroft, Jeffrey D. Ullman: Formal languages and their relation to automata. Addison-Wesley, 1969.
2. Maxime Crochemore, Christophe Hancart, Thierry Lecroq: Algorithms on Strings. Cambridge University Press, 2007.
3. Eric S. Raymond: The Art of Unix Programming. Addison-Wesley, 2003.
|Recommended optional program components:
|Languages required for the course completion:|
Total number of students assessed: 1383
doc. Ing. William Steingartner, PhD.
|Last modified: 01.09.2022|
|Approved by: person(s) responsible for the study program|