K-INFO
HU
EN
Login
Subject » BMEVISZMA04
Older versions Download TAD (PDF)

Languages and Automata

Nyelvek és automaták
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 BMEVISZMA04
Subject type —
Training Level —
Course types and hours (weekly/semester)
Course type lecture tutorial laboratory
hours (weekly) 3 0 0
type (linked/independent) — — —
Assessment type félévközi érdemjegy
Credits 4
Subject coordinator
DR. Friedl Katalin
position: egyetemi docens
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

Deterministic finite automaton (DFA)

Regular languages, their properties. 

Nondeterministic finite automaton (NFA), algorithm to convert it to DFA

Minimal DFA construction. Regular expressions and their connection to NFA

The existence of non-regular languages, pumping lemma 

Formal grammars, Chomsky hierarchy. Regular grammars 

Algorithm to construct NFA from regular grammar, and regular grammar from NFA. Context free 8CF9 grammars and languages, parse trees, ambiguous words, grammars, and languages.

Standardization of CF grammars:  algorithms to remove epsilon rules, unit rules, unneeded symbols

Chomsky normal form. Closure properties of CF languages

The existence of non CF languages. Pumping lemma for CF languages

Closure properties of CF languages. A simple parser: Cocke-Younger-Kasami algorithm. Pushdown automata (PDA)

Equivalence of PDA and CF grammars

Turing machine variations (one tape/multitape, deterministic/non-deterministic), their equivalence

Universal Turing machine. The notion of recursive (decidable) languages and recursively enumerable (recognizable) languages, examples. Diagonal language, universal language, halting problem.

The language classes R, RE, coRE, their connections, closure properties  

 The complement of the diagonal language. Theorem of Rice

Post correspondence problem.  Time complexity and space complexity of languages

 

 

 

To learn the basics of the theory of automata, the abstract definition, mathematical properties. To learn about formal languages and their connection to automata. To learn about the computational and practical consequences of Turing-machines. Emphasis is on theory and mathematical proofs.

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

3 hours lecture per week

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 algorithms
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 algorithms
General rules
Requirements: Two tests during the semester. For a passing grade one has to achieve at least 40% on each.  Additional possibilities: There are three retake occasions: one for each tests, and at the end of the semester a third when either one (but only one) can be  taken.
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.