Belépés címtáras azonosítással
magyar nyelvű adatlap
Formális nyelvek
A tantárgy angol neve: Formal Languages
Adatlap utolsó módosítása: 2006. július 1.
Tantárgy lejárati dátuma: 2015. január 31.
Műszaki Informatika Szak
Név:
Beosztás:
Tanszék, Int.:
Dr. Bach Iván
egy. docens
Számítástudományi és Információelméleti Tanszék
-
Bevezetés a számításelméletbe I., II.
A hallgatók ismerjék meg a számítástechnikai nyelvészet matematikai alapjait és a gyakorlati alkalmazások elvi korlátait.
A formális nyelv fogalma. A nyelvtan, mint végtelen nyelvek véges leírásának módszere. Chomsky féle nyelvosztályok. Automaták.
Reguláris nyelvek és véges automaták. A determinisztikus és a nem determinisztikus automaták ekvivalenciája.
Minimálautomaták és ezek unicitása. Kétirányban mozgó véges automata.
Reguláris nyelvek és reguláris halmazok ekvivalenciája. Műveletek nyelvekkel. A reguláris nyelvek zártsági tulajdonságai. Pumpálás.
Környezetfüggetlen nyelvek. Levezetési fa, nyelvtanok egyértelműsége.
Nyelvtanok átalakításai, normálformák. Veremautomaták. Determinisztikus és nem determinisztikus nyelvtanok, illetve nyelvek. Kettős pumpálás. A környezetfüggetlen nyelvek zártsági tulajdonságai.
A fordítás fogalma. Egyszerű és nem egyszerű szintakszis vezérelt fordítási sémák. Véges fordító, veremfordító. Jellemző nyelvtanok. Nyelvosztályok zártsága véges fordításra.
Általános elemzők: Earley algoritmus, Cocke-Younger-Kasami módszer.
Baloldali elemzés: LL(k) elemzés, faktorizáció.
Jobboldali elemzés: LR(k) elemzés, életképes prefixumok, prefix tulajdonságú nyelvek.
Precedencia elemzés, erős és gyenge precedencia.
Operátor precedencia.
Turing gépek és 0 osztályú nyelvek. Church tézis. A Turing gép megállási problémája. Algoritmikus eldönthetetlenség. A Post probléma.
A számítástechnikai nyelvészet algoritmikusan eldönthetetlen kérdései.
Előadás és gyakorlat. A tananyag egy része a gyakorlatokon kerül ismertetésre.
A szorgalmi időszakban:
A szorgalmi időszakban 50 pont szerezhető. Az egy nagy zárthelyi dolgozattal, melyet a félév közepén íratunk, 30 pontot lehet elérni. További 5 alkalommal villámzárthelyit íratunk a gyakorlatok első 20 percében. Ezekkel 5-5 pont szerezhető, de csak a 4 legjobb eredményét vesszük figyelembe.
A zárthelyi dolgozat pótolható. A pótzárthelyire a szorgalmi időszak vége előtt kerül sor. A villámzárthelyik pótlására nincs lehetőség.
A pótzárthelyit javító céllal a nagy zárthelyin részt vett hallgatók is megírhatják. Ebben az esetben a zárthelyi és a pótzárthelyi eredményének átlaga számít bele a félév során szerzett pontokba.
Az aláírást akkor kapja meg a hallgató, ha a félév során a megszerezhető 50 pontból (30 a nagy zárthelyin, 20 a villámzárthelyiken) legalább 20-at elért.
A zárthelyi bepótlására a vizsgaidőszak első hetében is lehetőség van.
Két évnél nem régebbi aláírást elfogadunk.
Az aláírást az első vizsgán, utóvizsga jelleggel is meg lehet szerezni. Ezzel a lehetőséggel csak az a hallgató élhet, aki az 5 villámzárthelyi, egy nagy zárthelyi és egy pótzárthelyi alkalmak közül legalább hármon megjelent és dolgozatot adott be.
A vizsgaidőszakban:
Az osztályzat a félévközi pontok és a vizsgadolgozat eredménye alapján a következőképpen alakul: az összpontszám egyik felét (50 pont) a vizsgadolgozat, a másik felét (nagy zárthelyi=30 pont + villámzárthelyik=20 pont) a félévközi eredmény adja. A jegyek: 85 ponttól jeles, 70 ponttól jó, 55 ponttól közepes, 40 ponttól elégséges, de minden, legalább elégséges jegyhez szükséges, hogy a vizsgadolgozat legalább 20 pontos legyen. A kreditpontok megszerzésének egyetlen feltétele a legalább elégséges osztályzat.
Akinek régebbről van aláírása, az választhat, hogy félév közben pontokat szerez vagy sem. Ha nem próbál pontokat szerezni, akkor a sikeres vizsga pontszámának duplázásával kap évvégi jegyet. Ha a félév közbeni munkával legalább 20 pontot gyűjt, akkor a számára kedvezőbb lehetőség szerint számítjuk az évvégi pontjait (vagy a vizsga duplázásával, vagy a félévi pontszám és a vizsga pontszám összeadásával). Ha a félévközi munkával nem szerzi meg az előírt 20 pontot, aláírása ekkor sem veszik el, ebben az esetben az évvégi pontjait a sikeres vizsga duplázásával kapja.
Aki az aláírást a vizsgaidőszakban szerzi meg, az félévi pontként 20 pontot kap, ehhez adódik a sikeres vizsga pontszáma, így születik az évvégi jegy. Aki javít, azaz a korábban megszerzett, legalább elégséges vizsgajegyét kiütteti az indexében, az a számára kedvezőbb módon (vagy a vizsga duplázásával, vagy a félévi és vizsgán szerzett pont összeadásával) számított összpontszám alapján kap jegyet.
Elővizsga: Nincs rá lehetőség.
Bach Iván : Számítástechnikai nyelvészet (Typotex Kiadó)
Bővebb irodalomjegyzék a fenti jegyzetben.
vima2208.rtf