Rekurzívak-e a természetes nyelvek?

A cikkben a szerzõ azt vizsgálja, hová esnek a természetes nyelvek a Chomsky-féle bonyolultsági hierarchiában. Bemutatja és elemzi a klasszikus és modern álláspontokat, és amellett érvel, hogy a természetes nyelvek leírhatóak még a véges automatáknál is szigorúbb nyelvtanokkal is.

Kálmán Lászlónak 50. születésnapjára

A kérdés háttere

Ebben a tanulmányban¹ a címben feltett kérdés körüljárását azzal kezdjük, hogy egy kicsit pontosabban megnézzük mi a rekurzivitás és mi a nyelv. Természetesen ha rekurzión csak annyit értünk, hogy valamilyen konfiguráció ismétlődik, ismétlődhet, akkor a válasz triviális. Ilyen ismétlődésre jó példa a koordináció, hiszen a Láttuk Jánost és Pétert és Zolit és ... konstrukció addig terjeszthető amíg ki nem fogyunk a lélegzetből.² Hogy tovább tudjunk lépni ezen a trivialitáson, a rekurzivitás a matematikában megszokott definíciójánál maradunk: rekurzíve felsorolható az amire Turing-gépet (Turing Machine, TM) be lehet programozni. Azok akik a Turing-gépeket elsősorban a logikából ismerik (emlékeztetőül: a Turing gép egy végtelen szalagból és az ennek mozgatását/írását/ olvasását szabályozó véges kontroll-automatából áll), gyakran hozzá vannak szokva, hogy ezek (bináris) számokon operálnak. Turing eredeti definiciója ezt a megkötést nem tartalmazza: a szalagra tetszőleges véges szimbólumhalmaz elemeit írhatjuk. Egy ilyen szimbólumhalmazt ábécé-nek nevezünk: a legegyszerűbb ábécé csupán egy elemet (az 1 szimbólumot) tartalmaz, iletve a szalag bármely kockája üresen is maradhat (0 szimbólum). Szimbólumok egymás után írásával (konkatenáció) képezzük a füzéreket (strings), ideértve a szimbólumot egyáltalán nem tartalmazó üres füzért (empty string), amely nem tévesztendő össze a helyköznek/nullának megfelelő fehér szimbólummal (blank symbol): előbbi hossza (a benne szereplő szimbólumok száma) nulla, utóbbié 1.

Egy rögzített TM által megadott formális nyelv azon füzérek halmaza, melyeket a gép szalagjára írva a program véges idő alatt vagy megáll úgy, hogy a szalag üres (üres szalaggal való elfogadás), vagy kitüntettet állapotok valamelyikébe kerül (állapothalmazzal való elfogadás), vagy egy előre rögzített füzér ill. erre a célra fenntartott OK szimbólum kiírásával reagál (jelzéssel való elfogadás). Bár egy adott nyelvhez természetesen másféleképpen kell programozni a TM-et aszerint, hogy melyik elfogadás-definíciót választjuk, összeségében a TM-ek által megadható nyelvek halmazát ez a döntés nem befolyásolja. Sokkal fontosabb az a kérdés, hogy az elfogadás ellentéteként az explicit elutasítást választjuk (pl. * szimbólum kiírásával) vagy belenyugszunk abba, hogy bizonyos dolgokról a számításhoz megengedett (tetszőlegesen hosszú) idő lejárta előtt nincs igen/nem döntésünk. Ha megköveteljük, hogy a TM explicit OK/* jelzést adjon minden bemenő füzérre (ahogy a nyelvészeti irodalomban is * jelzi az agrammatikus példamondatokat), akkor a rekurzív nyelvek családjához jutunk, ha megelégszünk az egyoldalú visszajelzéssel akkor a bővebb, rekurzíve felsorolható nyelvosztályhoz jutunk.

A nyelv fogalmának alapos, mind filozófiai mind nyelvészeti szempontból kielégítő definíciója messzire vezetne, de céljainkhoz ez nem is szükséges, hiszen matematikai kérdést csupán matematikai objektumokról lehet feltenni. A formális nyelv a természetes nyelvek bevett matematikai modellje: a nyelvészeti alkalmazásokban az ábécé elemeire gyakran mint a természetes nyelv fonémáira (általában néhány tucat elem) illetve szófajaira (gyakran több ezer különböző elem) gondolunk. A formális nyelvi modell mesterséges (programozási) nyelvekre is alkalmazható: ilyenkor az ábécé elemei általában a rögzített utasítások (do, if, while), relációk (>, <), szintaktikai egyértelműsítők (zárójelek, idézőjelek), változónevek, és aritmetikai kifejezések - ez utóbbi osztályoknak maguknak is megvan a saját formális nyelve, mely a programnyelv egészébe be van ágyazva. A természetes nyelvről fontos plusz információ, amit most első közelítésben elhanyagolunk, hogy a szavak és nagyobb konstrukciók közt különféle kapcsolatok állhatnak fenn, és hogy a szavaknak/mondatoknak mérhető gyakorisága/valószínűsége van. A formális nyelvekről immár formális szigorúsággal felvethető az a kérdés, hogy vajon végesek vagy végtelenek, és ha végtelenek akkor rekurzívak ill. rekurzíve felsorolhatóak-e?

A kérdés, ha nem is egészen ebben a formában, de egyidős a formális nyelvészeti kutatással, melynek alapjait még Panini (i.e. 520-460) vetette meg, nagyjából két évszázaddal azelőtt, hogy Euklidész megvetette a matematika alapjait. A Mahabhashya (Nagy Kommentár) az első fennmaradt Panini-magyarázat, i.e. 200 körülről.³ A bevezető részben Patañjali azzal kezdi, hogy egyszerűbb a helyes (grammatikus) alakokat felsorolni, mint a helyteleneket, majd azt a kérdést veti fel, hogy hogyan kell ezt megcsinálni: szedjük listába a helyes alakokat? Nem, ez túlságosan nehéz lenne. Mert mint tudjuk, Brhaspati (az istenek tanára) ezer égi évig (360,000 földi évig) tanított Indrának egy olyan munkát, amely felsorolta a helyes szanszkrit kifejezéseket, és még így sem jutott a végére. Akkor hogy lehetne most, amikor az emberek még száz nyarat sem élnek meg, íly módon tanítani?

Igaz ugyan, hogy egy adott nyelv eddig elhangzott/leírt mondatai véges halmazt alkotnak, de a nyelvészek körében teljes az egyetértés (és mindig is az volt) hogy az ezen a tényen alapuló naív modell érdektelen, hiszen minket nem csak egy létező korpusz leírása érdekel, hanem az is, hogy predikciókat tegyünk a még el nem hangzott (vagy le nem írt) mondatok halmazára nézve is. Ha megadjuk a koordináció szabályait, pl. a perl, python és más programnyelvekből ismert szabályos kifejezésekkel (regular expressions), akkor máris egy olyan nyelvtanunk van amely végtelen sok, eddig még nem hallott/látott mondat elfogadhatóságára tesz tesztelhető jóslatot.

1956 előtt a matematikusok a végtelen nyelvek algoritmikus megadására csupán két módszert tartottak számon: a véges automatákon (vagy ami ugyanaz, szabályos kifejezéseken) keresztüli, illetve a Turing-gépes definíciót. A véges automaták által elfogadott nyelvekre lehet úgy is gondolni, mint az olyan TM-ek által elfogadott nyelvekre amelyek csak olvasni tudnak, de a szalagot nem írhatják (természetesen ehhez az állapothalmazzal való elfogadás-definíciót kell használni). Az ilyen TM csak véges sokféle részeredmény megjegyzésére képes, hiszen a memóriakapacitását behatárolja a kontroll-automata (véges) állapottere. Míg az írni is tudó TM-eken alapuló definíciónál egyáltalán nem mindegy, hogy annak kétoldalú (rekurzív) ill. egyoldalú (rekurzíve felsorolható) változatát tekintjük, a csak olvasni tudó TM-ek (véges automaták) körében ez a különbség nem vezet más nyelvosztályhoz: akár egyoldalú akár kétoldalú definicióval az úgynevezett hármas típusú (type 3) nyelveket kapjuk.⁴

Másképp fogalmazva: egy tetszőleges $T$ ábécé fölötti hármas típusú $L$ nyelv komplementuma (tehát azon füzérek halmaza melyek csupán $T$ elemeiből állnak de nem tartoznak az $L$ halmazba) is hármas típusú lesz, míg a rekurzíve felsorolható másnéven nullás típusú) nyelvekre ez nem igaz, van olyan amelyiknek a komplementuma nem nullás típusu (rekurzíve nem sorolható fel). Bár ez nem a bevett nómenklatúra része, az olyan 0 típusú nyelveket melyeknek komplementuma is 0 típusú ezentúl 0.5 típusúnak hívjuk - mint ez egyszerűen belátható a 0.5 épp a rekurzív nyelvek osztálya. Chomsky (1956,1957) érdeme, hogy e két szélsőség, az írni is tudó illetve a csak olvasni tudó TM-ek közé, egyes nyelvészeti technikák matematikai formába öntésével, két újabb osztályt iktatott, ezek lesznek az egyes illetve kettes típusu nyelvek.

Az egyes típust Chomsky a XIX századi neogrammatikus hangtörvények formalizálására általa bevezetett környezetfüggő nyelvtan (context sensitive grammar, CSG) segítségével írta le: ezekben a füzérek egyes elemeit a szabályok át tudják alakítani akkor, ha az elemek környezetére bizonyos feltételek teljesülnek. Pl. a magyar szavak végén a zöngétlen mássalhangzók zöngésülnek, ha zöngés mássalhangzóval kezdődő rag (vagy szóösszetétel második eleme) követi őket: vaskalap, vazsgolyó (ejtésben), vassal, de vazsból. A környezetfűggő nyelvtanok ezt a tényt egy $s\rightarrow zs /\_Z$ szabállyal ragadják meg, melynek jelentése cseréld ki s-t zs-re ha jobboldali kontextusa Z.⁵

A Turing-gépek perspektívájából nézve az 1 típust úgy nyerjük, hogy engedélyezzül az írást (a részeredmények tárolását a gép szalagján) de csak bizonyos korlátok közt: a TM-nek csak akkora memóriát teszünk írhatóvá amekkora a bemenő füzér. Úgy is fogalmazhatunk, hogy a TM író/olvasófeje nem léphet ki az eredeti bemenő füzér határai közül, bár technikailag egyremegy hogy pontosan ennyit, vagy a bemenő hossz tetszőleges de rögzített konstansszorosát engedélyezzük. Az így nyert lineárisan korlátolt automata (linear bounded automaton, LBA) osztály által definiált formális nyelvcsaládról sokáig nyitott kérdés volt, hogy zárt-e a komplementációra, mígnem Szelepcsényi (1987) és tőle függetlenül Immerman (1988) nem igazolták, hogy minden 1 típusú (LBA által megadott) $L$ nyelv $\overline{L}$ komplementumához is található LBA amivel $\overline{L}$ adható meg.

A kettes típust Chomsky a közvetlen összetevős elemzés (immediate constituent analysis, ld. Wells 1947, Harris 1951) formalizálására szintén általa bevezetett környezetfüggetlen nyelvtan (context free grammar, CFG) segítségével definiálta. Ezekben a nyelvtanokban szintén $x\rightarrow y$ alakú szabályok vannak⁶ de most mindenféle megszorítás nélkül: egy ilyen szabály mindig alkalmazható, függetlenül attól, hogy $x$ előtt és után milyen szimbólumok állnak. A környezetfüggetlen nyelvek osztályát már kicsit nehezebb a TM-fogalom egyszerű korlátozásával behatárolni, de ha egy TM-nek a bemenő füzérnek csupán az olvasását engedélyezzük, viszont a TM-et kiegészitjük egy veremmemóriával, akkor éppen ezt a (kettes) nyelvosztályt nyerjük. Megemlítjük, hogy ez az osztály nem zárt komplementációra: pl. (legalább kételemű ábéce fölött) az az $L_N$ nyelv amely a nem négyzetes füzérekből áll (tehát elemei nem állnak elő $xx$ formában, ahol $x$ tetszőleges füzér) kettes típusú, míg komplementuma, tehát az az $L_I$ nyelv ami pontosan a négyzetes ( $xx$ alakú) füzérekből áll, nem lesz kettes típusú. Az eddigieket összefoglalva már kész is áll az eredeti Chomsky hierarchia melyet itt bővített formában hozunk (az eredeti 0-3-hoz itt hozzátett nyelv- illetve nyelvtan-osztályokról később lesz szó):

típus	nyelvosztály	definíciós eszköz	nyelvtan
0	rekurzíve felsorolható (r.e.)	TM (egyoldalú)	tetszőleges
0.5	rekurzív	TM (kétoldalú)
1	környezetfüggő (CSL)	lin. korl. aut (LBA)	környezetfűggő (CSG)
1.5	enyhén környezetfüggő (MCS)	beágyazott veremautomata	linear indexed, CCG, LTAG
2	környezetfüggetlen (CSL)	veremautomata (PDA)	környezetfüggetlen (CFG)
3	véges állapotú (regular)	véges automata (FSA)	FSG, szabályos kifejezések
4A	nem-számláló (non-counting)	counter-free automata	nem-számláló
4B	véges	lista	lista

Ez a tipológia annyiban hierarchikus, hogy a csökkenő számoknak egyre bővülő eszköztár felel meg: minden nyelv amit le tudunk írni 3. típusú nyelvtannal az leírható 2. típusúval is, amit le lehet írni 2. típusúval az leírható 1. típusúval is, és persze minden amit egyáltalán le lehet írni nyelvtannal az leírható Turing-géppel is. Ha nem így lenne, akkor a nyelvtanok ellenpéldát adnának a Church tézisre, hiszen a nyelvtan egyfajta algoritmus (megfelel az algoritmus intuitív definíciójának) és ha nyelvtanilag definiálható lenne olyan halmaz (formális nyelv) amely TM segítségével nem definiálható, akkor a TM nem adná az algoritmus intuitív fogalmának kielégítő formalizálását.⁷ Chomsky érdeme, hogy a címben felvetett triviális kérdést egy sokkal izgalmasabbra cserélte fel: hova esnek a nyelvek a Chomsky-hierarchiában? (amit ő természetesen még nem hívott így).

Az 1. szakaszban ismertetem a klasszikus álláspontot, miszerint a természetes nyelvek <2 típusúak, az e mellett felhozott a klasszikus érveket, és a klasszikus ellenérveket, elsősorban Pullum és Gazdar (1982) alapján. A 2. szakaszban a modern érveket és ellenérveket tárgyalom, végül a 3. szakaszban a függőségi nyelvtan egy olyan, Paninira visszamenő változatát definiálom, amely alapján a mai (részint elméleti, részint számítógépes nyelvészeti) gyakorlat jobban megérthető.

A klasszikus álláspont

Chomsky nemcsak felvetette a problémát, de úgy vélte, hogy kielégítően meg is oldotta. Azt az állítást, hogy a harmadik típus nem elégséges a természetes nyelvek leírásához az un. középponti beágyazás (center-embedding) jelenségével indokolta: matematikailag bebizonyította, hogy az olyan CF nyelvtanok amelyek megengednek $X \rightarrow aXb$ alakú levezetést (ahol tehát a végeredményben a kiinduló $X$ $a$ és $b$ közé beágyazva jelenik meg) szükségképpen túllépnek a 3. típuson (különben ez nem igaz, CF, azaz 2. típusu nyelvtan is generálhat olyan nyelvet amely szabályos kifejezésekkel, azaz 3. típusú nyelvtannal is megadhatók) majd rámutatott, hogy az angolban a vonatkozói mellékmondatok középponti beágyazott helyzetben is megjelenhetnek: a rat that stole the cheese, a cat a woman loves, the cheese that a rat (that a cat (that a woman loves) chased) stole. A Mondattani szerkezetek (1957, magyarul 1999) ezért írja, hogy

Nemcsak nehéz, de lehetetlen olyan [véges automatát] létrehozni amely az angol nyelv valamennyi nyelvtanilag helyes mondatát létrehozná, és csak azokat. (...) E tétel azt állítja, hogy a nyelv (...) Markov-folyamat koncepciója elfogadhatatlan, legalábbis a nyelvtan céljaira. (p 24)

(Az érvelés nyelvtani része, különösen a zárójelezés nélkül gyakorlatilag érthetetlen the cheese that a rat that a cat that a woman loves chased stole már annak idején is sok vitát váltott ki, erre a kérdésre majd a 2.3 szakaszban térünk vissza.) Chomsky (1957) nem sok kétséget hagyott a felől sem, hogy szerinte a CF nyelvtanok sem elégségesek a feladathoz:

[A CF nyelvtanok] angol nyelvre történő alkalmazásának korlátait tovább vizsgálva, meggyőzően igazolható, hogy ezek a nyelvtanok olyan reménytelenül bonyolultak, hogy teljesen érdektelenné válnak, hacsak nem építünk beléjük [transzformációkat]. (p 50)

Patañjali teljes joggal elvárhatta olvasóitól a védikus bölcsesség ismeretét és feltétel nélküli elfogadását, de a modern nyelvészektől már kicsit furcsábbnak tűnik a mert mint tudjuk érv használata.

Since there seems to be no way of using [context free rules] to represent [AUX-initial interrogatives, which are] an obviously significant generalization about English, we can be sure that CFGs cannot possibly represent all the significant aspects of language structure. We must introduce a new kind of rule that will permit us to do so. (Akmajian and Heny 1975:86)

Dehát honnan tudjuk, hogy a segédigés kérdőmondatok (Did John visit the school? v.ö. John visited the school) nem állíthatók elő környezetfüggetlen nyelvtannal? Nos ezt nem tudjuk, nem is tudhatjuk, hiszen az alábbi CFG éppen ezeket adja ki: $Q \rightarrow Aux S[-tense]; S[-tense] \rightarrow NP VP[-tense]; VP[-tense] \rightarrow V[tr,-tense] NP; VP[-tense] \rightarrow V[intr,-tense]$ . Itt Aux a segédige, NP (noun phrase) a szokásos módon újraírható mint tulajdonnév (John, Mr. Smith) vagy mint névelős köznév (the boy, a man), V[intr] az intranzitív (tárgyatlan) igék osztálya, V[tr] a tranzitívaké, az időjel hiánya pedig a szabály része.

The single most important contribution to the development of linguistic theory in the [20th] century is [the demonstration of] the inadequacy of CFGs as a model of linguistic structure. (Selkirk 1977:285)

Nem lenne ezt jobb előbb bebizonyítani még mielőtt mint a huszadik századi nyelvtudomány legnagyobb fejleményét ünnepeljük? Pullum és Gazdar (1982) ma már klasszikus "meztelen a király" cikkükben sorra vették az irodalomban fellelhető érveket (a táblázat utolsó oszlopában a hiba sorszáma látható):

szerző	év	kulcsszó	hiba
Y. Bar-Hillel and E. Shamir	1960	respectively	2
P. Postal	1964	mohawk	3
A. Zwicky	1963	zillion	2
N. Chomsky	1963	középfok	1,3
R. Huybregts	1976	holland	3
J. Elster	1978	$\pi$	2

és egyenként kimutatták róluk, hogy tarthatatlanok, méghozzá három egymással gyakran összefüggő hiba miatt. Ezek közül az első és legfontosabb az, hogy időről időre 1. az eredeti érvelés matematikailag hibás. Erre jó példa Chomsky saját érvelése, ami azon a jelenségen alapul, hogy az angolban a középfokú összehasonlításban nem szeretjük ha ugyanazzal hasonlítunk: This desk is wider than that chair is tall de *This desk is wider than that chair is wide. Ez utóbb esetben inkább az összehasonlítás alapját képező NP törlésével dolgozunk: This desk is wider than that one. Hogy ez a "nem szeretjük" mit jelent arra majd később visszatérünk (Pullum és Gazdar igen szórakoztatóan írnak arról, ahogy Chomsky később megváltoztatta az itt még csillaggal hozott mondatok grammatikalitásáról való véleményét), most fogadjuk el, hogy a jelenség valóban így igaz. A baj az, hogy az így kijelölt $L_N$

nyelv nem ellenpélda CF nyelvre, csak a komplementuma $L_I$

lenne az, de a CF család nem zárt komplementumra! Quandoque bonus dormitat Homerus.⁸

A második, hasonlóan gyilkos ellenérv az, hogy 2. Az eredeti érvelés összekeveri a szintaxist a szemantikával. Ezt most Zwicky (1963) példáján illusztráljuk, amely a trillió, kvadrillió, kvintillió (trilliárd, kvadrilliárd, kvintilliárd) és hasonló nagy számok nyelvi kifejezésén alapul. Nem tudjuk, mi a legnagyobb ilyen, de nem is fontos hogy elkötelezzük magunkat egy konkrét -illió (vagy -illiárd) mellett, legyen a zillió a legnagyobb szótári szó ami $1000^n$ -t fejez ki. Ennek a négyzete egyzillió zillió. Még ennél is nagyobb szám az egyzillió zillió egyzillió egy. De az *egyzillió egyzillió zillió nem legális számnév, mert a nagyobb zillió-hatványokat kell előbb mondani.

$\begin{displaymath}\{p_1 z^{n_1}p_2 z^{n_2} \ldots p_r z^{n_r}\vert n_j > n_{j+1}\} \not\in CF \end{displaymath}$

A probléma az, hogy ez nem nyelvtani, hanem matematikai tudás. Későn sajátítjuk el, és nem is mindenki tudja aki egyébként kompetens anyanyelvi beszélő. Ugyanez a baj Elster a $\pi$ tizedestört kifejtéséről szóló érveivel (ennek részleteit ld. Pullum és Gazdar cikkében), és a híres respectively konstrukción alapuló érveléssel is, mely szerint a John, Mary, and Bill are a widower, widow, and widower respectively típusu mondatokban, ha csupán a nem szerint egyértelmű keresztnevekre szorítkozunk és elvárjuk hogy widower csak hímnemű, widow csak nőnemű legyen, akkor a grammatikus mondatok halmazát az $xx$ halmazba tudjuk képezni ahol $x$ tetszőleges füzér a kételemű hímnem, nőnem halmaz felett (tehát a nem-CF $L_I$ nyelvet nyerjük).

Külön hangsúlyozzuk, hogy a nyelvtan nem törődik a tényekkel, az a mondat hogy Einstein was a great physicist grammatikailag ugyanolyan helyes mint az, hogy Einstein was a great physician bár tényszerűleg az egyik igaz a másik hamis. Az Anna özvegyember mondat valóban nehezen értelmezhető (hacsak nem Boris Viannál találjuk) de ebben a nehézséget nem a mondatszerkezet hanem a világról való ismereteinkkel való összeférhetetlenség okozza. Igen, de nem lenne elképzelhető olyan nyelv, ahol a nem szerinti egyeztetés nem szemantikai, hanem grammatikai kérdés? Miután pontosan tudjuk, hogy számtalan ilyen nyelv van, a respectively-n alapuló érvelés esetleg az angolban nem, de mondjuk a spanyolban tarthatónak tűnik. A probléma az, hogy nyelvtani alapon már a két felsorolás hosszúságának megegyezése sem garantálható, hiszen a Going left to right, the last two people in the line are John and Bill respectively mondat helyes, szemantikailag is és grammatikailag is, pedig a respectively-vel összekapcsolt felsorolások nem tartalmaznak ugyanannyi elemet, hiszen a baloldalt egyetlen NP, the last two people, áll szemben a jobboldalt két NP-vel, John and Bill.

A harmadik ellenérv annyiban hasonló az elsőhöz, hogy ez is egy matematikai hibát pécéz ki: 3. az eredeti érvelés empirikusan lyukas. Általában, ahhoz hogy egy nyelv nem-CF voltát igazoljuk, nem elég rámutatni egy nem-CF résznyelvre, mert a Chomsky hierarchia nem zárt tartalmazásra, egy nem-CF nyelv résznyelve is lehet CF, és egy CF nyelv résznyelve is lehet nem-CF (és hasonlóan a hierarchia többi tagjára, a véges nyelvek családjának kivételével). A problémát az egyik legkorábban felfedezett és legizgalmasabb jelenségkör, a mohawk főnév-inkorporáció (Postal 1964) erősen egyszerűsített változatán illusztráljuk. A nyelvészetben szokatlan módon elhagyjuk az eredeti mohawk példamondatokat és csupán magyarított glosszákat adunk (az eredeti mondatok megtalálhatók Postalnál és kritikusainál). A mohawk nyelv a tárgyas ige tárgyát gyakran megismétli az igei csoportba beépítve: Nekem ház-tetszik a ház "Tetszik a ház". Az inkorporált elem lehet pronominalizált formában is: Nekem idea-tetszik ez "Egyetértek ezzel". Postal azt állította, hogy az inkorporált főnév megegyezik az inkorporálatlan (külső) tárggyal, a mohawk tehát $L_I$ nyelv. Igenám, de az általa vizsgált nem az egyetlen inkorporatív konstrukció, be lehet építeni teljes birtokos szerkezeteket is: Nekem János-ház-tetszik János ház "Tetszik János háza". Ez még nem lenne baj, de az ilyen szerkezetekből a birtokos elhagyható: Nekem ház-tetszik János "Tetszik János háza", és ez betölti a lyukakat, a nyelv tehát végsősoron nem $L_I$ jellegű. (Már itt megjegyezzük, hogy a mohawk egyik legalaposabb leíró nyelvésze, Floyd Lounsbury (idézi Reich 1969) szerint az érvelés eleve fiktív annyiban, hogy az inkorporáció nem iterálható, a kétszeres inkorporálásnál az egyik tő mindig egy idióma része, de ez most a birtokos szerkezet által felszinre hozott probléma szempontjából közömbös, a jelenségre később térünk majd vissza.)

A modern érvek

Pullum és Gazdar cikke csupán negatív érveket hozott, és retorikailag nyitva is hagyta a kérdést hogy vajon a második Chomsky-típusba beleférnek-e a természetes nyelvek. Sokkal fontosabb volt ennél, hogy ezek a szerzők megalapozták az általánosított frázis-struktúra nyelvtan (generalized phrase structure grammar, GPSG) elméletét, amelyben a nehéz, mindaddig a természetes nyelvek nem-CFL voltának igazolására használt nyelvi problémákat mint pl. a hosszútávú függőség (unbounded dependecy) sorra oldották meg. De nem tartott sokáig, amíg megjelentek az új érvek, elsősorban Shieber (1985) a svájci némettel foglalkozó, Culy (1985) a bambara nyelvvel foglalkozó, és Beesley és Karttunen (2000) a malájjal foglalkozó cikkei - ez utóbbi érdekessége, hogy nem a szintaxisban, hanem már egy lépéssel előbb, a morfológiában (ahol az füzérek a szavak az ábécé pedig a morfémák) mutat nem-CF konstrukciót.

Elődeikkel ellentétben ezek a munkák már matematikailag hibátlanok, tisztán nyelvtani (nem pedig szemantikai) tényeken alapulnak, és empirikusan sem lyukasak. Ez azonban nem jelenti azt, hogy a kérdést végképp eldöntik, hiszen másfajta gyengeségeik azért még lehetnek, és mint látni fogjuk, vannak is. A modern ellenérvek két nagy csoporra oszthatók, egyrészt a megfigyelhető bizonytalan grammatikai státusz, a "nem szeretjük" körüli problémák, ezekről korlátozott iterativitás néven beszélek 2.1-ben, másrészt a nagyon kis gyakoriság okozta problémák, ld. 2.2. Egy kicsit előreugorva megjegyezzük, hogy ezek az ellenérvek egyben a klasszikus középponti beágyazási példákat is kilövik, így nemcsak a 2. osztály elégtelensége, hanem az ennél jóval kisebb 3. osztály elégtelensége (és ezzel Chomsky eredeti, a Markov-modellezéssel szembeni dörgedelmei) is kérdésessé válnak. De mielőtt erre rátérnénk (ld. 2.3), lássuk a modern ellenérveket részletesebben.

Bizonytalan grammaticitás, korlátozott iterativitás

A klasszikus generatív felfogásban éles dichotómia van a grammatikus (OK) és az agrammatikus (*) mondatok közt. Hogy egy konkrét kifejezés hova esik, azt a nyelvész intuíciója (ill. az anyanyelvi informáns) dönti el. Sajnos a Shieber, Culy, és mások által vizsgált szerkezetek mindegyike nagyon hamar olyan kifejezésekhez vezet, ahol a nyelvész/informáns intuíciója elbizonytalanodik. Ezt az önmagában érdekes tényt Chomsky (1965) a performancia és a kompetencia közti megkülönböztetéssel próbálta magyarázni, de nyitva hagyta azt a kérdést, hogy ha a beszélők fejében lévő grammatikai apparátus olyan nagyon komplex, akkor miért pont ezek a kifejezések okoznak nehézséget, míg egyéb tetszőlegesen nagyra növelhető konstrukciók (mint a koordináció) nem.

Az általános performancia-probléma fontos speciális esete az, amit itt korlátozott iterativitás-nak fogunk nevezni, lássuk ezt egy egyszerű beágyazási példán. Tekintsük először elemi kijelentések valamilyen S halmazát: Meleg van, esik az eső, kigyulladt a ház,..., majd kezdjük el bővíteni ezt attitűdöt kifejező kijelentésekkel: Az hogy S (az) hazugság/egy nagy hülyeség/biztos/kétségbeejtő/... Az első iterációban egészen rendes, értelmes magyar mondatokat nyerünk: Az hogy esik az eső az kétségbeejtő, az hogy kigyulladt a ház az hazugság,... Mindez valamiféle $S\rightarrow$ Th S (D) Att szabály felvételét indokolja, ahol Th az "Az hogy" formatíva, D az "Az" formatíva, Att pedig az attitüdinális kifejezések "kacsa, hétszentség, elszomorító, ..." gyűjteménye. A második iterációban ezek a szabályok már különös eredményeket hoznak: ??Az hogy az hogy meleg van az kacsa az elszomorító - mit is jelent ez? Hát, vidámabbak lennénk ha a hír nem lenne kacsa (hanem tényleg meleg lenne). Ez még talán rendben is van, bár a kognitív folyamat már inkább a rejtvényfejtésre mint a szokásos nyelvi megértésre emlékeztet. De ha még egyszer-kétszer iterálunk, az amúgy olyan remekül működő automatikus parzerünk végképp fejreáll: ????Az hogy az hogy az hogy esik az eső az bizonytalan az hétszentség az hazugság és csak a rejtvényfeltés marad.

A jelenséget, hogy a középponti beágyazás igen hamar kivezet az emberi ésszel felfogható (és előállítható) mondatok köréből (ennek korai kisérleti igazolását ld. Marks 1968) az teszi fontossá, hogy mindenütt ezt találjuk: más nyelveknél, és más konstrukcióknál is. Karlsson (2007) 16 nyelvre kiterjedő vizsgálatai szerint az írott nyelvben maximum háromszoros, a beszélt nyelvben maximum kétszeres beágyazást találunk. Ez tehát egy erős, jól replikálható nyelvi jelenség, és ha ezt tudjuk, akkor már mindegy is, hogy a kompetencia vagy a performancia részének tekintjük.

Chomsky (1965) még elsősorban azért különítette el a kompetenciát a performanciától (ezzel nagy, évtizedekig nem csillapuló módszertani vihart kavarva) hogy a középponti beágyazások korlátozott iterativitását átsorolhassa a performanciába, és ezáltal (hiszen minket mint nyelvészeket a kompetencia modellezése jobban érdekel) fenntarthasson egy olyan idealizációt ami kivezet a szabályos kifejezések közül.

A naív matematikai modell, ami az iterálást egyáltalán nem korlátozza, most finomításra szorul, pl. egy olyan számlálóra ami legfeljebb egyszeres vagy kétszeres iterációt engedélyez. Tulajdonképpen mindegy is, hogy hánynak választjuk ezt a $d$ iterációs korlátot, kettőnek vagy ötnek, hiszen a kétszer és az ötször iterált konstrukciók közötti különbséghalmazban már csak marginális (grammatikailag kétes és szemantikailag csak igen nehezen értelmezhető) füzérek lesznek.

Gyakoriság

A klasszikus érvelés (Chomsky 1957:2.4) szerint a nyelvtan világában a gyakoriság nem számít, hiszen colorless green ideas sleep furiously és furiously sleep ideas green colorless egyaránt nulla gyakoriságúak, de előbbi grammatikus utóbbi pedig nem. Ha ez igaz, a grammaticitás nem jellemezhető valószínűséggel, hiszen itt mindkét példa gyakorisága nulla. A tudomány történetének különös fintora (bővebben ld. Pereira 2000), hogy ezt a minden matematikusnak azonnal láthatóan hibás érvelést a szakma évtizedekig nem tudta, nem merte megkérdőjelezni. Hol a hiba? Ott, hogy a nulla empirikus frekvenciából nem következik nulla valószínűség.

Természetesen mindkét mondatnak nagyon kicsi a valószínűsége. Ez már abból is kiderül ha a mért szógyakoriságokat egymástól függetlennek tekintő (unigram) modellt vesszük, hiszen ekkor a mért szógyakoriságokat összeszorzva $2.14\cdot 10^{-25}$ körüli értéket nyerünk - ebből már látható, hogy mindenképpen nagyon nagy mintára lenne szükség ahhoz, hogy az ilyen jellegű mondatok előbukkanjanak. Ha most a nyilván túlságos egyszerűsítést jelentő függetlenségi feltevést elhagyjuk, annál is inkább, hiszen az unigram modellek még nem különítik el a szavak permutálásával nyert fűzérekre jósolt valószinűségeket (a statisztikai nyelvmodellezés alapvető technikáit illetőn ld. pl. Jelinek 1997) és szópárokon, szóhármasokon alapuló (bigram, trigram) modelleket veszünk, akkor a két mondat valószinűségére egyre inkább eltérő értékeket kapunk. Saul és Pereira (1997) számításain szerint a két valószínűség hányadosa mintegy $2\cdot 10^5$ , tehát a Chomsky által grammatikusnak ítélt változat mintegy kétszázezerszer valószinűbb agrammatikus társánál. Ezen az intervallumon belül bárhol (tehát meglepően robusztusan) meghúzhatjuk a határt úgy, hogy a colorless green ideas sleep furiously grammatikusnak, a furiously sleep ideas green colorless pedig agrammatikusnak minősüljön, pusztán valószinűsége alapján. Igaz ugyan, hogy ezt a valószinűséget matematikai modelleink csupán becsülni tudják, direkt méréséhez nem áll rendelkezésünkre elégséges minta, de ez módszertanilag épp oly kevéssé zavar minket mint az, hogy a nap belsejének a hőmérsékletét sem tudjuk hőmérővel megmérni.

Gyakran találkozunk a fenti hibás érvelés konverzével is, mely szerint "a bizonyíték hiánya nem a hiány bizonyítéka" - abból, hogy egy kifejezést a korpuszban nem találunk meg, még nem tudjuk megmondani, hogy a kifejezés csak ritka, vagy tényleg agrammatikus. Ha ez igaz, akkor az intuícióra (akár a nyelvészére akár az informánséra) való hivatkozás a nyelvészet kikerülhetetlen része. Természetesen ez az érv ugyanúgy nem állja meg a helyét mint az előző. Hol a hiba? Vegyük például azt az érdekes jelenséget, hogy az angol cost igének nincs passzívuma: The book cost thirty dollars. *Thirty dollars were cost(ed) by the book. Való igaz, hogy a passzívum hiányát nyelvi intuíciónk világosan jelzi - a fentebb tárgyalt példákkal ellentétben itt senki nem fog a csillagok elhelyezésén vitatkozni. De tényleg csak az jelzi? Stefanowitsch (2006) az alábbi kétszer kettes kontingencia-táblát közli:

	Passive	Active	Total
cost	0	63	63
-cost	13,861	122,627	136,488
Total	13,861	122,690	136,551

Ebből bármilyen megszokott statisztikai teszttel (pl. Fisher-Yates) kiszámolható, hogy a bal felső sarokban álló nulla nem véletlen nulla, az a tény hogy a cost esetén nem találunk passzív alakot szignifikáns ( $p < 0.01$

)

Külön figyelmet érdemel az, hogy a statisztikai és a performancia-alapú megfontolások igen hasonló eredményre vezetnek: ha csak annyit teszünk fel, hogy az $S\rightarrow$ Th S (D) Att szabály mondjuk 1/1000 valószínűséggel működik,⁹ akkor iterációjának már csak egy a millióhoz, kétszeri iterációjának már csak egy a milliárdhoz az esélye.

A fennmaradó esetek

Bár a CFG-ellenpéldák eredeti bestiáriumából nem sok maradt, van mégis egy olyan konstrukció a hollandban, amelyre már Huybregts (1976) felhívta a figyelmet (ez mind szinkron nyelvtanát mind történeti kialakulását tekintve közeli rokona a Shieber (1985) tárgyalta svájci német példának) és amely változatlanul sok fejtörést okoz, annak ellenére, hogy mint füzérhalmaz (stringset) környezetfüggetlen. A holland hogy-os mellékmondatok szórendjét, beágyazott infinitivális tárgyak esetén, kereszteződő szerkezet jellemzi:

... dat Jan de kinderen zag zwemmen

hogy Jan a gyerek.PL lát.PAST úszik.INF

hogy Jan látta a gyerekeket úszni

... dat Piet de kinderen hielp zwemmen

hogy Piet a gyerek.PL segít.PAST úszik.INF

hogy Piet segítette a gyerekeket úszni

... dat Marie de kinderen liet zwemmen

hogy Marie a gyerek.PL küld.PAST úszik.INF

hogy Marie elküldte a gyerekeket úszni

A kereszteződés (crossed dependency) azt jelenti, hogy a dependenst a fejjel összekötő gráf-élek (pl. Jan és lát illetve gyerek és úszik közt) keresztezik egymást, hiszen nem a gyerek lát és Jan úszik hanem épp fordítva. Az ilyen szerkezeteket rekurzíve egymásba is lehet helyettesíteni:

... dat Jan Piet de kinderen zag helpen zwemmen

hogy Jan Piet a gyerek.PL lát.PAST segít.INF úszik.INF

hogy Jan látta Piet-et (amint) segíti a gyerekeket úszni

... dat Jan Piet Marie de kinderen zag helpen laten zwemmen

hogy Jan Piet Marie a gyerek.PL lát PAST segít.INF elküld.INF

hogy Jan látta Piet-et Marie-nak segíteni elküldeni úszni a gyerekeket

Igaz ugyan, hogy a nyelv CF ( $a^nb^n$

), de a struktúra nyilván nem az, mert az i-edik $a$

-edik

-hez kapcsolódik, nem pedig az $n-i$

-edikhez, míg egy CF nyelvtan, pl. $S\rightarrow aSb; S\rightarrow ab$ ez utóbbi struktúrát állítaná elő. A modern matematikai nyelvészet számos eljárást kidolgozott az ilyen esetek kezelésére: itt csupán a beillesztés (wrap, ld. Bach 1981), a fa-adjunkció (tree adjunction, ld. Joshi 2003), és a kombinátoros kategoriális grammar (combinatory categorial grammar, ld. Steedman 2001) módszereit említem. Külön érdekesség, hogy ezeknek az egymástól gyökeresen eltérő eljárásoknak mindnek van olyan variánsa amelyik ugyanahhoz az enyhén környezetfüggő (mildly context sensitive, MCS) nyelvosztályhoz vezet (ld. Vijay-Shanker, Weir, and Joshi 1986, Weir 1992) melynek a fenti táblázatban a másfeles típusszámot adtuk.

A Chomsky-hierarchiában a másfeles (CFG-nél bővebb, de a CSG-nél szűkebb) nyelv- és nyelvtanosztályok szisztematikus vizsgálatát Joshi (1985) kezdeményezte, bár az ilyenek egyik legfontosabb előzményét, a lineáris indexált nyelvtanokat, már Aho (1968) bevezette. Ezzel a kiinduló kérdésünk körüli vita annyiban nyugvópontra is jutott, hogy ennél bővebbet ma senki nem javasol a természetes nyelvek kezelésére (maga Chomsky sem, akinek "minimalista" elmélete ugyancsak egy enyhén környezetfüggő osztályra mutat). Ebből következik az a fentebb a 7. lábjegyzetben már megelőlegezett tény, hogy a nyelvészeti alkalmazások körében a Church-tézis státuszát befolyásoló eredmények nem várhatók - a természetes nyelvi füzérek grammatikalitása ugyanis polinomiális időben eldönthető.¹⁰

Ugyanakkor vannak szép számmal (és ide tartozik a szerző is) akik ezt a megoldást nem tartják kielégítőnek, hiszen mérnöki szemszögből teljesen elfogadhatatlan, hogy a hatalmas erőforrások bevetését olyan konstrukciók kezelésével indokoljuk, amik 3-4 iteráció fölött soha nem fordulnak elő, és alatta is csak olyan össz-valószínűséggel ami messze alatta marad a jelenlegi nyelvtanok hibaszázalékának (Kornai 1998). Az előadás hátralevő részében tehát egy olyan modellt vázolok, amely nemcsak alkalmas a hollandhoz hasonló esetek leírására, hanem oda teszi az erőforrásokat ahol azokra valóban szükség van, a grammatikai függőségek (dependencies), nem pedig az összetevőszerkezet vizsgálatához.

Régi-új függőségi nyelvtan

A modern olvasó számára elsősorban Tesniére (1959) alapján lehet ismert a függőségi nyelvtanok alapgondolata, miszerint az egyes összetevők egymáshoz való viszonya nem szimmetrikus, hanem általában egy főtag (a régens, a konstrukció feje) és egy vagy több bővítmény (dependens) kapcsolatáról van szó. Gaifman (1965) a függőségi nyelvtanok egy olyan változatát formalizálta, mely végeredményben CFG értékű - ezek ilyen formában nem adnak megoldást arra a problémára amit a holland infinitívuszi bővítmények jelentenek. De a függőség gondolata jóval Tesniére előtt is ismert volt, és Gaifman formalizmusa távolról sem az egyetlen lehetséges megközelítés. Itt most Panini mélyeset (karaka) elméletének adjuk egy olyan megfogalmazását, amely a holland problémát (is) kezelhetővé teszi. Panini hat mélyesetet különböztet meg (az első oszlopban megszokott angol nevüket, az utolsóban a definiáló szútrát adjuk meg):

Agent	kartr	aki független	(1.4.54)
Goal	karman	amit A elsősorban kíván	(1.4.49)
Recipient	sampradana	aki adásnál szem előtt van	(1.4.32)
Instrument	karana	a leghatékonyabb eszköz	(1.4.42)
Locative	adhikarana	a hely	(1.4.45)
Source	apadana	a rögzített pont melytől el	(1.4.24)

Említést érdemel, hogy a felszini eseteket a mélyesetekhez kötő reláció nem egyértékű: pl. a John rented a room FOR_I three hundred dollars FOR_L three months FOR_PP a barbershop mondatban három for prepozícióval (felszini esettel) kapcsolódó dependens is van, de ezekhez különféle mélytesetek tartoznak: three hundred dollars instrumentális, three months lokatív (ebbe a temporális lokáció is beleértetik) és a célhatározói barbershop nem is tartozik a rent ige vonzatkeretéhez, hanem szabad határozó. A magyar bérel ige teljes vonzatkeretét az alábbi táblázatban foglalhatjuk össze:

bérel:	vki	vkitől	vmit	vmeddig	vmennyiért
	A	S	G	L	I

Főmondatbeli előfordulásaik alapján világosan látható, hogy a holland zag, hielp, liet igék egyáltalán nem különlegesek: a lehető legegyszerűbb tranzitív (A+G esetkeretű) igékről van szó, és zwemmen is egyszerű intranzitív (A esetkeretű) ige. Ha van valami különlegessége a liet és társainak, akkor az az, hogy tárgyuk (Goal) nem csak nominális, hanem infinitívuszi konstrukció is lehet. Ez egyébként más nyelvekben sem ritka, pl. latin video/audio/scio patrem venire, bár az egyes nyelvek az infinitívuszi dependenseket nem pontosan ugyanazokra az igékre teszik lehetővé, v.ö. a magyar látom/hallom/*tudom apát jönni példákkal (a magyarról bővebben ld. Kálmán C. et al 1989).

Ha az egyes mélyesetekre mint egy hat dimenziós tér bázisvektoraira gondolunk,

mélyeset	vektor	default felszini eset
Agent		NOM
Goal		ACC
Recipient		DAT
Instrument		INS
Locative		LOC
Source		ABL

akkor pl. a zwemmen ige a $(-1,0,0,0,0,0)$

vektorral kódolható. Tehát de kinderen.NOM zwemmen (A gyerekek úszni/úsznak) 0-vektort ad: előbbi INF utóbbi S értékű. Általában, a dependens akkor tudja csak a régens esetkeret valamely nyitottan álló pozícióját betölteni, ha ehhez a megkívánt mélyesettel (formalizmusunk szerint tehát a megfelelő dimenzióban) kapcsolódik: ha ez teljesül akkor nullvektort nyerünk, ha nem nem. Innentől a holland leírásának feladata igen egyszerű: zag, hielp, liet mind a $(-1,-1,0,0,0,0)$

vektornak felelnek meg, és zag(Jan_A, (de kinderen zwemmen)_G) Jan látta a gyerekeket úszní, hasonlóan hielp `segítette', liet `elküldte'. Ez tehát valódi nyelvi rekurzió, a szó matematikai értelmében (ismételt függvényalkalmazás) lát(Jan_A, (segít(Piet_A, (a gyerekek úszni)_G))) és nehézséget csupán a szórend elkódolása jelenthet, ehhez mi is a beillesztés, pontosabban a `fej mellé illesztés' (head wrap, ld Pollard 1984) mechanizmusát használjuk (Kálmán és Kornai 1984).

Nem vizsgáltuk meg a vektorösszeadáson alapuló dependencia-ellenőrző algoritmus bonyolultságát, de a fej mellé illesztés (akárcsak a többi enyhén környezetfüggő mechanizmus tipikusan $O(n^6), O(n^7)$ elemzési lépést igényel, szemben a CFG $O(n^3)$ időigényével (Roach 1984). Még ennél is nagyobb probléma az, hogy a CF és MCS formalizmusok ekvivalenciaproblémája eldönthetetlen: nincs olyan algoritmus, ami két ilyen nyelvtanról megmondaná, hogy ugyanazt a nyelvet generálják-e (Hopcroft 1969). Ebből következik, hogy általános esetben a CFG (és erősebb) formalizmusok nem tanulhatók: ha ugyanis lenne olyan tanulóalgoritmus ami nyelvtant rendel a nyelvhez, akkor tetszőleges két nyelvtan mindegyikén lefuttathatnánk azt a triviális algoritmust ami a nyelvtan alapján felsorolja a nyelvet, és már csupán annyit kellene ellenőrizni, hogy a tanulóalgoritmus ugyanazt a nyelvet rendeli-e ezekhez. Más szóval, a tanulóalgoritmus meglétéből a nyelvtan-ekvivalencia eldönthetősége következne, pedig az ekvivalencia-probléma CF (és annál bonyolultabb) nyelvtanokra eldönthetetlen.

Összefoglalás

A gyakorlati nyelvmodellek, melyek gépi tanulással készülnek, véges állapotúak, sőt egyes elméletek (Kornai 1985, 2007) még ennél is szigorúbb megkötést tesznek, a nem-számlálás (non-counting, counter freeness, ld. McNaughton és Papert 1971) feltételét: azt várjuk el, hogy ha a nyelvben szerepel az $ab^4c$ füzér akkor az $ab^5c$ is szerepeljen. Ez a feltétel (melyet a Chomsky-hierarchiába 4A számmal illeszthetünk be) olyan erős, hogy még a véges (4B) nyelvek egy részét is kizárja. A főbb nyelvtan-fajták generatív kapacitását az alábbi táblázatban foglalhatjuk össze (a kérdőjelek bizonyítatlan sejtést jelentenek):

szó-összerakás	mélyebb elemek	jelentés-alapú
ICA 1.5	DG 1.5	generative semantics 0
(generalized) PS 2	lexical-functional 2	Montague 0
categorial 2	transformational 0	Cyc-L 0?
combinatory cat 1.5	case 2	KR 0
head 1.5	arc pair 0?	Wierzbicka 4A?
head-driven PS 0	linking ?
(lex'd) tree-adj 1.5	Panini 4A?

Hova esnek tehát a természetes nyelvek a Chomsky-hierarchiában? A leginkább laza (a legbonyolultabb nyelvtanokat megengedő) elméletek szerint a másfeles, a legszigorúbb (csak igen egyszerű nyelvtanokat megengedő) elméletek szerint a 4A típusba. Annyi bizonyos, hogy a szintaktikai bonyolultságot a korlátozott iterativitás nagyban megköti: ha elfogadjuk, hogy a beágyazás/keresztezés foka legfeljebb $d$

(és ezzel a kikötéssel csupán néhány nagyon ritka és bizonytalan grammatikai értékű konstrukciót zárunk ki függetlenül attól, hogy $d=3,4$

vagy 5 választással élünk) akkor a hármas típus már biztosan elegendő és a 4A-ra sem ismerünk ellenpéldát. A kérdést ebben a formájában immár fél évszázada vizsgálja a nyelvtudomány, és várakozásaink szerint a következő évtizedekben a figyelem egyre inkább a szigorú nyelvtanok felé fog fordulni, hiszen tanulóalgoritmusok bizonyíthatóan csak ezekhez lehetségesek.

Jegyzetek

1. A szerző 2007 okt 19-i habilitációs előadásának kibővített változata. Az eredeti előadás adottnak vett bizonyos, a műegyetemi hallgatóktól joggal elvárható előismereteket, melyek meglétét itt nem tételezzük fel. Azok az olvasók akik a formális nyelvek matematikai elméletének alapjait ismerik (magyarul ld. pl. Bach (2002), angolul Salomaa 1973) a bevezető részt elég ha átfutják.
2. A leghosszabb ilyen mondat állítólag a második világháború végén az arlingtoni nemzeti temetőben hangzott el, ahol felolvasták a hősi halottak névsorát.
3. Volt egy korábbi is, a Vartikka (Katyayanától, i.e. 3-400 körül) de ezt csak a hivatkozásokból tudjuk, sajnos nem maradt fenn.
4. Fentebb utaltunk arra, de nem bizonyítottuk, hogy a szabályos kifejezések és a véges automaták illetve írni nem tudó TM-ek ugyanazt a nyelvosztályt adják meg. Ez egy klasszikus eredmény (Kleene 1956), amelynek bizonyítása meghaladná e cikk kereteit. Lentebb még számos ilyen ekvivalencia-eredményre hivatkozunk, általában a forrás megjelölése nélkül - az érdeklődő olvasó ezeknek Bach (2002) és Salomaa (1977) mellett szinte bármelyik elméleti számitógéptudományi alapvetésben (pl. Gruska 1997) vagy a wikipédiában is utánanézhet.
5. Itt $Z$ az összes zöngés mássalhangzó rövidítése - arra nézve hogy miért nem kell annyi szabályt külön felvenni ahány zöngétlen mássalhangzó csak szóbajöhet mint a szabály bemenete ld. Chomsky and Halle 1968.
6. Szigorú értelemben itt is és az egyes típusnál is meg kell különböztetni az un. terminális és nemterminális szimbólumokat, ennek részleteit most figyelmen kívül hagyjuk.
7. Megjegyezzük, hogy a nyelvészet irányából nem várhatóak a Church tézist illetően izgalmas fejlemények, mert mai tudásunk szerint mindent amire a nyelvészetben szükség van már környezetfüggő (egyes típusú) nyelvtannal, tehát LBA-val is meg lehet oldani.
8. Házi feladat: Konstruáljunk olyan CFG-t ami a fenti $L_N$ -t adja meg.
9. Ez a szám most hasraütéssel készült, de egy nagyobb korpuszban nem lenne nehéz leszámlálni az ilyen konstrukciókat és ez által arányukról pontosabb becsléshez jutni.
10. Egészen pontosan a hármas típusú nyelvtanokkal leírható nyelvek eldöntésproblémája valós idejű, az analízisben szokásos nagy ordo jelöléssel, (ld http://hu.wikipedia.org/wiki/O_jeloles) $O(1)$ , a kettes típusúaké legfeljebb $O(n^3)$ , és a másfeles típusúaké legfeljebb $O(n^7)$ , és ez utóbbi eredmenyek meg javithatóak, pl. gyors szorzás felhasználásával a második típusnál helyett $O(n^{2.81})$ is elérhető, ld. Valiant. (1975).

Irodalom

Aho, Alfred (1968): "Indexed grammars - An extension of context-free grammars," Journal of the ACM 15(4) 647-671.
Akmajian, Adrian and Frank Heny (1975): An introduction to the principles of transformational syntax, MIT Press.
Bach, Emmon (1981): "Discontinuous constituents in generalized categorial grammars," Proc. NELS II, 1-12.
Bach, Iván (2002): Formális nyelvek, Typotex.
Beesley, Kenneth and Lauri Karttunen (2000): "Finite-state non-concatenative morphotactics," Proc. 5th SIGPHON Wkshp 1-12.
Chomsky, Noam (1956): "Three models for the description of language," I.R.E. Transactions on Information Theory IT-2.
Chomsky, Noam (1957): Syntactic Structures, Mouton, The Hague.
Chomsky, Noam (1965): Aspects of the Theory of Syntax, MIT Press.
Chomsky, Noam and Morris Halle (1968): The Sound Pattern of English, Harper and Row.
Culy, Christopher (1985): "The complexity of the vocabulary of Bambara," Linguistics and Philosophy 345-351.
Gaifman, Haim (1965): "Dependency structures and phrase structure grammars," Information and Control 304-307.
Gruska, Jozef (1997): Foundations of Computing, Thompson Scientific.
Harris, Zellig (1951): Methods in Structural Linguistics, University of Chicago Press.
Hopcroft, John E. (1969): "On the Equivalence and Containment Problems for Context-Free Languages," Mathematical Systems Theory 3(2) 119-124.
Huybregts, Rini (1976): "Overlapping dependencies in Dutch," Utrecht Working Papers in Linguistics 1 224-265.
Immerman, Neil (1988): "Nondeterministic Space is Closed Under Complementation," SIAM J. Comput. 17 935-938.
Jelinek, Frederick (1997): Statistical Methods for Speech Recognition, MIT Press.
Joshi, Aravind (1985): "How much context-sensitivity is necessary for characterizing structural descriptions?" in: Dowty, Karttunen and Zwicky (eds) Natural Language Processing, Cambridge University Press.
Joshi, Aravind (2003): "Tree adjoining grammars," in Mitkov (ed): Handbook of Computational Linguistics, Oxford University Press 483-500.
Karlsson, Fred (2007): "Constraints on multiple center-embedding of clauses," Journal of Linguistics 43(2) 365-392.
Kálmán C. György, Kálmán László, Prószéky Gábor, Nádasdy Ádám (1989): "A magyar segédigék rendszere," Általános Nyelvészeti Tanulmányok 17 49-103.
Kálmán, László and Kornai, András (1985): "Pattern matching: a finite state treatment of `context sensitive' phenomena," Unpublished manuscript, Hungarian Academy of Sciences Institute of Linguistics, presented at the 1985 Vienna Syntax Workshop.
Kleene, Sthephen C. (1956): "Representation of events in nerve nets and finite automata," In: Shannon - McCarthy (eds): Automata studies, Princeton University Press 3-41.
Kornai, András (1985): Natural languages and the Chomsky Hierarchy, in: M. King (ed): Proceedings of the 2nd European Conference of the Association for Computational Linguistics 1-7.
Kornai, András (1998): "Quantitative Comparison of Languages," Grammars 155-165.
Kornai, András (2007): Mathematical Linguistics, Springer Verlag.
Marks, Lawrence (1968): "Scaling of grammaticalness of self-embedded English sentences," Verbal Learning and Verbal Behavior 7(5) 965-967.
McNaughton, Robert and Seymour Papert (1971): Counter-free automata, MIT Press.
Pereira, Fernando (2000): "Formal grammar and information theory: Together again?" Philosophical Transactions of the Royal Society, series A 358 1239-1253.
Pollard, Carl (1984): "Generalized Phrase Structure Grammars, Head Grammars, and Natural language," PhD dissertation, Stanford University, August 1984.
Postal, Paul (1964): Constituent Structure, Mouton.
Pullum, Geoffrey and Gerald Gazdar (1982): "Natural languages and context free languages," Linguistics and Philosophy 4 471-504.
Reich, Peter (1969): "The finiteness of natural languages," Language 45 831-843.
Roach, Kelly (1984): "Formal Properties of Head Grammars," Unpublished manuscript, Stanford University, presented at the Mathematics of Languages workshop at the University of Michigan, Ann Arbor, Oct. 1984.
Salomaa, Arto (1973): Formal Languages, Academic Press.
Saul, Lawrence and Fernando Pereira (1997): "Aggregate Markov Models for statistical language processing," Proc. 2nd Conf on Empirical Methods in Natural Language Processing 81-89.
Selkirk, Elizabeth (1977): "Some remarks on noun phrase structure," in: Culicover, Wasow, and Akmajian (eds) Formal Syntax, Academic Press.
Shieber, Stuart (1985): "Evidence against the context-freeness of natural language," Linguistics and Philosophy 333-343.
Steedman, Mark (2001): The syntactic process, MIT Press.
Stefanowitsch, Anatol (2006): "Negative evidence and the raw frequency fallacy," Corpus Linguistics and Linguistic Theory 61-77.
Szelepcsényi, Róbert (1987): "The method of forcing for nondeterministic automata," Bull. EATCS 33 96-100.
Tesnière, Lucien (1959) Eléments de Syntaxe Structurale, Klincksieck.
Valiant, Leslie (1975): "General context-free recognition in less than cubic time," Journal of Computer and System Sciences 10 308-315.
Vijay-Shanker, K., David Weir, Aravind Joshi (1986): "Tree adjoining and head wrapping," Proc. 11th coference on Computational Linguistics, Bonn, Germany.
Weir, David J. (1992): "Linear context-free rewriting systems and deterministic tree-walking transducers," Proc. ACL92 136-143.
Wells, Roulon (1947) "Immediate constituents," Language 23 321-343.