A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Subject name (Hungarian, English) |
Nyelvek és automaták
Languages and Automata
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subject code | BMEVISZMA12 | ||||||||||||
| Subject type | — | ||||||||||||
| Training Level | — | ||||||||||||
| Course types and hours (weekly/semester) |
|
||||||||||||
| Assessment type | félévközi érdemjegy | ||||||||||||
| Credits | 5 | ||||||||||||
| Subject coordinator |
DR. Friedl Katalin
position: egyetemi docens
contact:
friedl.katalin@vik.bme.hu
|
||||||||||||
| Responsible department |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Faculty | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Subject website | cs.bme.hu/la | ||||||||||||
| Primary curriculum type | — | ||||||||||||
| Direct prerequisites – Strong prerequisite | none | ||||||||||||
| Direct prerequisites – Weak prerequisite | none | ||||||||||||
| Direct prerequisites – Parallel prerequisite | none | ||||||||||||
| Direct prerequisites – Milestone prerequisite | none | ||||||||||||
| Direct prerequisites – Exclusion | none |
Objectives
Programme
1. Concepts of alphabet, word and language. Deterministic finite automaton. Class of regular languages and their closure properties to
union, intersection, difference, complement.
2. Incomplete, nondeterministic and epsilon-transiton finite automata, their equivalence.
The class of regular languages is closed to concatenation and transitive closure.
3. Equivalence relation on words and states of a finite automaton, their relation. Minimal automata.
4. Regular expressions, their equivalence with finite automata. Proof of non-regularity, the pumping lemma.
5. Formal grammars, the Chomsky hierarchy. Regular grammars.
Decision questions about regular languages (empty, finite, does it contain the given word, are two languages equal).
6. Context-free grammars and languages. Simplification of CF grammars: Epsilon rules, chain rules, elimination of redundant symbols.
7. Closure properties of context-free languages. Non context-free languages, the pumping lemma.
8. Non-deterministic and deterministic stack automata. CF grammar and stack automata. Deterministic CF languages.
9. Deciding inclusion: Cocke-Younger-Kasami algorithm and its efficiency. General
analysts.
10. Ambiguity of CF grammars and languages, examples, relation to determinism.
11. Deterministic and non-deterministic Turing machines. Determinization of non-deterministic Turing machines.
12. Definition of R and RE classes, examples. The Church-Turing thesis.
13. Equivalence of single and multitape Turing machines. Famous languages: diagonal, universal, halting language.
14. Closure properties of R and RE. Relationship between R, RE, coRE, further examples.
15. Rice's theorem and its applications. Post correspondence problem.
16. Algorithmic quiestions in CF grammars: decidable and undecidable problems.
17. Generative languages and Turing machines, context-sensitive languages and the relation to linearly constrained Turing machines.
18. Space- and time-bounded Turing machines. Space-time theorem. TIME, SPACE, NTIME NSPACE classes. Their closure properties, and relationship.
19. Relation of P, NP, PSPACE, EXPTIME classes. Witness theorem for the class NP. Karp reduction, Cook-Levin theorem
on NP-completeness of SAT. Other NP-complete languages
20. Relation of Turing machines to the RAM model, Relation between time bounds.
21. Repetition, Reserve.
The course covers the most important types of automaton and the basics of formal grammar. It introduces the relationships between automata and grammars and the limits of their applicability. Students will be introduced to the main theoretical foundations necessary for the construction of translation programs. In the context of Turing machines, they will also learn about problems that are undecidable and indecidable in algorithms.
(1) Familiarisation with the automata and grammars discussed, illustrated by examples.
(2) Understanding the relationships between different automata and grammars.
(3) Applying the techniques learned.
(4) The ability to select and apply the appropriate tool for a given problem.
Learning outcomes
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Knowledge
No learning outcomes recorded.
Skills
No learning outcomes recorded.
Attitudes
No learning outcomes recorded.
Autonomy and responsibility
No learning outcomes recorded.
Oktatási módszertan
Lecture, but some of the details (proofs) must be learnt independently from the notes provided.
Weekly practice exercises (not to be handed in) to help learning and check understanding.
Tanulástámogató anyagok
Online források
Michael Sipser: Introduction to the theory of computation, Thomson Course Techn., 2006.
Recommended preliminary knowledge for completing the subject
Knowledge type competencies
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
Basic knowledge of graphs, complexity classes P and NP
Skill type competencies
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Recommended (non-compulsory) preliminary competencies
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
Basic knowledge of graphs, complexity classes P and NP
General rules
Requirements:
Two tests during the semester. For a passing grade one has to achieve at least 40% on each.
Additional possibilities:
There is a retake for both tests.
Assessment methods
In-term assessments
No detailed assessments provided.
Weight of in-term assessments
No weights provided.
Exam-period assessments
No detailed assessments provided.
Weight of exam elements
No weights provided.
Grade calculation
No grade thresholds provided.
Attendance requirements
No attendance requirements provided.
Rules for retake and resubmission
Not provided.
Short description
Not provided.
Detailed description
Not provided.
Recommended courses
Not provided.
Workload to complete the subject
No workload breakdown provided.
Validity of subject requirements
Requirements valid from:
—
Requirements valid until:
—
Curriculum placement
No curriculum placements recorded for this subject version.