Tantárgy kódja

PMB1217

Tantárgy neve

Formális nyelvek, automaták

Tantárgy angol neve

Formal Languages and Automata

Kredit

4

Félévi követelmény

Vizsga

Heti óraszám

2 + 2

Elmélet + Gyakorlat

Ajánlott félév

1

Cél

A tantárgy keretein belül megismerik a hallgatók a Chomsky-féle osztályozás szerinti nyelvek és az automaták fő jellemzőit, alkalmazásukat. Képesek lesznek grammatikákat, automatákat definiálni, implementálni a tanult algoritmusokat és találkoznak a gyakorlatban megjelenő nyelvekkel .

Cél angol

The aim of course is to be know the bases of the formal languages.

Tartalom

Formális rendszerek és automaták főbb típusai. Nyelvek, nyelvtanok, normál alakok. Automaták és nyelvek kapcsolata. Chomsky-féle nyelvosztályok. Műveletek nyelvekkel, nyelvalgebra. Elemzők és felismerők, nyelvtani algoritmusok. Lindenmayer rendszerek. Néhány fontos nyelvészeti módszer és eredmény: Kleene tétele, Bar-Hillel lemma, Early-féle algoritmus, közelítő szövegegyeztetések, Lyon algoritmus. Számítástudományi alkalmazások.

Tartalom angol

Formal language, Markov-algorithm, Chomsky generative grammar, emptyword lemma, Bar-Hillel lemma, Turing machines

Számonkérés

vizsga

Számonkérés angol

examination

Irodalom

Bach Iván: Formális nyelvek, TYPOTEX Kiadó, Budapest, 2001. Demetrovics János, Jordan Denev, Radiszlav Pavlov: A számítástudomány matematikai alapjai, Tankönyvkiadó, Budapest, 1989. Falucskai – Kuki - Tarnay: Bevezetés a formális nyelvek és automaták alkalmazásába, MTA Sz-Sz-B Tud. Test., Nyíregyháza, 1993. Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon Kiadó, Szeged, 1999.

Irodalom angol

Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39 Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1    Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1    Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1    Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510   Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39 Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1 Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1 Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1 Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510 Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746 M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2 Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267

Tantárgyfelelős intézet kódja

MII

Tantárgyfelelős oktató

Dr. Falucskai János