kifejezéselmélet

A kifejezéselmélet a formális nyelvek és az automataelmélet kutatása. Formális nyelvnek nevezünk egy adott véges betűkészlet felett definiált olyan szövegek halmazát, amelyet szabályokkal lehet leírni vagy felismerni. A nyelvek leírására különféle grammákat és számítógépes modelleket használnak, például véges automatákat, veremmel rendelkező automata modelleket és Turing-gépeket. A terület célja a nyelvek osztályainak feltárása, a nyelvi felismerés és a feldolgozás elveinek megértése, valamint a kapcsolatok feltérképezése a nyelvtípusok között.

A meghatározó fogalom a Chomszkij-hierarchia: négy fő nyelvtípust különít el reguláris nyelvek (Type-3), kontextusfüggetlen nyelvek (Type-2), kontextusfüggő nyelvek (Type-1) és rekurzívan felső (Type-0) nyelvek. Ezeket különböző modellek írják le: véges automaták és reguláris kifejezések a reguláris nyelvekre, veremes automaták a kontextusfüggetlenekre, lineárisan korlátozott automaták a kontextusfüggőkre, és Turing-gépek a rekurzívan felső nyelvekre. Minden magasabb szint leírható az alacsonyabb szint nyelveinek általánosításával, de a dönthetőségek és a feldolgozás igényei is nőnek.

Fontos eredmény a pumpelési lemma reguláris és kontextusfüggetlen nyelvekre, amely segít megállapítani, hogy egy nyelv mely osztályba tartozhat. Tagadásához és felismeréséhez gyakran CYK-parszolást vagy hasonló algoritmusokat használnak a kontextusfüggetlen nyelvek esetében. A dönthetőségi problémák közül sok a teljes Turing-gépes nyelvekre nem dönthető.

Alkalmazások közé tartozik a fordítók és nyelvi feldolgozók tervezése, a formális verifikáció és a hardver-szoftver modellezés, valamint a nyelvészeti kutatások és a problémamegoldás elméleti alapjainak megalapozása. A kifejezéselmélet sokszor találkozik a gyakorlat igényeivel és elvárásaival.