Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Formale Sprachen

    A tantárgy angol neve: Formal Languages (In German)

    Adatlap utolsó módosítása: 2006. július 1.

    Tantárgy lejárati dátuma: 2015. január 31.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Műszaki Informatika Szak

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIMA2602 3. 2/2/0/v 5 1/1
    3. A tantárgyfelelős személy és tanszék Dr. Recski András,
    4. A tantárgy előadója

    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

    5. A tantárgy az alábbi témakörök ismeretére épít

    -

    6. Előtanulmányi rend
    Kötelező:
    TárgyEredmény( "BMEVIMA1235" , "jegy" , _ ) >= 2 VAGY TárgyEredmény( "BMEVIMA1205" , "jegy" , _ ) >= 2 VAGY TárgyEredmény( "BMEVIMA1601" , "jegy" , _ ) >= 2 VAGY TárgyEredmény( "BMEVIMA1602" , "jegy" , _ ) >= 2

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:

    Einführung in die theoretische Informatik I., II.

    7. A tantárgy célkitűzése

    A hallgatók ismerjék meg a számítástechnikai nyelvészet matematikai alapjait és a gyakorlati alkalmazások elvi korlátait.

    8. A tantárgy részletes tematikája

    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érlet 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águ 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.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    Előadás és gyakorlat. A tananyag egy része a gyakorlatokon kerül ismertetésre.

    10. Követelmények

    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. A dolgozatot nem osztályozzuk, de az elvárt teljesítmény legalább 12 pont elérése. 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.

    Orvosilag igazolt távolmaradás esetén 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.

    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 nem élhet az a hallgató, aki egyetlen villámzárthelyit sem írt, vagy egyetlen zárthelyit sem írt,

    vagy 12 pontot el nem érő zárthelyi eredményét nem kísérelte meg javítani.

    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 a félév során a nagy zárthelyi és a villámzárthelyik megírásával gyűjti a pontokat, és ekkor évvégi jegye a félévi pontokból és a vizsgadolgozatból adódik; vagy a vizsgadolgozatra kapott pontok duplázásával keletkező pontszám alapján kér jegyet. Erről az első villámzárthelyi megírása előtt kell döntenie. Ha úgy dönt, hogy új aláírást (és a vele járó pontokat) kíván szerezni, akkor korábbi aláírását a tárgy félvben nem ismerjük el. Aki megbukik egy vizsgán, illetve az, aki az aláírást az első vizsgán szerzi meg, év végi jegyét a sikeres vizsgán elért pontjainak duplázásával kapja.

    Elővizsga: Nincs rá lehetőség.

    13. Jegyzet, tankönyv, felhasználható irodalom

    Bach Iván : Számítástechnikai nyelvészet (egyetemi jegyzet)

    Bővebb irodalomjegyzék a fenti jegyzetben.

    15. A tantárgy tematikáját kidolgozta

    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

    vima2602.rtf