Předmět Kapitoly z formálních jazyků a automatů (KMI / PGSFJ)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / PGSFJ - Kapitoly z formálních jazyků a automatů, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).

Materiál	Typ	Datum	Počet stažení

Obsah

Předmět je určen především studentům doktorského studia jako výběr pokročilých partiíteorie formálních jazyků, gramatik a automatů. Vyžaduje úvodní znalost elementárníchkonceptů této problematiky vymezených v bodě 1 níže. Studenti se v předmětu seznámís pokročilými technikami vhodnými k (i) vědecké práci v oblasti jakýchkoli výpočetních modelů se vztahem k jazykům a automatů, jako je analýza přirozeného jazyka, strojový překlad, molekulární výpočty, modely molekulární samoorganizace atd. (ii) aplikacím formálních jazyků v oblastech jako počítačová grafika, rozpoznávání obrazu, překladače aj.1. Shrnutí elementárních pojmů teorie formálních jazyků a automatů.Formální jazyk, formální gramatika (regulární, bezkontextová, kontextová, bez omezení), konečný automat, zásobníkový automat, Turingův stroj.2. Uzávěrové a algebraické vlastnosti jazyků. Abstraktní třídy jazyků - AFL jako silný nástroj pro studium vlastností jazykových tříd.3. Paralelní gramatiky. Lindenmayerovy systémy, jejich typy, vlastnosti a aplikace (růstové modely, počítačová grafika, fraktální množiny apod.)4. Gramatiky s řízeným odvozením. Programované gramatiky, kontextem regulované gramatiky, jejich varianty a třídy generovaných jazyků.5. Deterministické, nedeterministické a alternující automaty. Případové studie: konečný automat a Turingův stroj. Charakterizace výpočetní síly uvedených variant prostředky teorie složitosti, vztah k paralelním počítačům.6. Automaty s počítadly, jejich univerzalita a vztah k Turingovým strojům, slepé automaty s počítadly.

Získané způsobilosti

1. ZnalostPopsat a důkladně pochopit principy a metody vybraných partií teorie formálních jazyků.

Literatura

Kozen D. C. Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.Minsky M. L. Computation: Finite and Infinite Machines. Englewood Cliffs, N.J., Prentice-Hall, 1967. ISBN 67012342.Rozenberg G., Salomaa A. (Eds.). Handbook of Formal Languages Vol. 1. Springer, 1997. ISBN 3-540-60420-0.Rozenberg G., Salomaa A. (Eds.). Handbook of Formal Languages Vol. 2. Springer, 1997. ISBN 3-540-60648-3.http://algorithmicbotany.org/Hopcroft J. E., Motwani R., Ullmann J. D. Introduction to Automata Theory, Languages, and Computation. Pearson Education, 2003. ISBN 0-321-21029-8.Dassow J, Paun G. Regulated Rewriting in Formal Language Theory. Springer, 1990. ISBN 3-540-51414-7.Greibach S. A. Remarks on blind and partially blind one-way multicounter machines. Theoretical Computer Science, 7:311--324, 1978.

Garant

doc. RNDr. Vilém Vychodil, Ph.D.

Vyučující

doc. Ing. Petr Sosík, Ph.D.doc. RNDr. Vilém Vychodil, Ph.D.