15. fejezet - Számítástudományi alapok

Tartalom

15.1. Formális nyelvek és generatív nyelvtanok
15.1.1. Ábécé, szavak és nyelv
15.1.2. Nyelvműveletek
15.1.3. Átíró és generatív rendszerek
15.1.4. A Chomsky hierarchia
15.1.5. Nyelvtanok normálformái
15.1.6. Nyelvosztályok tulajdonságai
15.2. Automaták
15.2.1. A véges automaták
15.2.2. A veremautomaták
15.2.3. A Turing-gép
15.3. Bonyolultságelméleti alapfogalmak

Ennek a résznek a célja az, hogy röviden összefoglaljuk, áttekintsük az alapvető számítástudományi fogalmakat, amelyek egy része a könyv különböző fejezeteiben központi szerepet játszik. (Ez természetesen nem, vagy csak részben helyettesíti az erre a témára koncentráló alapozó könyv(ek) olvasását, ajánljuk pl. a Dömösi Pál, Falucskai János, Horváth Géza, Mecsei Zoltán, Nagy Benedek: Formális Nyelvek és Automaták, Kelet-Magyarországi Informatika Tananyag Tárház, 2011. tankönyvet...)

Először egy jelölési kérdést tisztázunk: A könyvben ℕ jelöli a természetes számok halmazát: beleértve a 0-t és a pozitív egészeket, ℤ jelöli az egészek számok halmazát, ℚ a racionális és ℝ a valós számok halmazát.

15.1. Formális nyelvek és generatív nyelvtanok

15.1.1. Ábécé, szavak és nyelv

Minden formális leírás azzal kezdődik, hogy tisztázzuk, milyen szimbólumokat használhatunk a leírás során.

21. Definíció. Szimbólumok tetszőleges, nem üres, véges halmazát ábécének nevezzük, és V-vel jelöljük, a V elemeit az ábécé betűinek mondjuk. A V ábécé betűiből kirakott (véges) szavak halmazát, a λ üresszót is beleértve, V*-gal jelöljük. Az L-et V ábécé feletti formális nyelvnek nevezzük, ha L ⊆ V*. Egy w = a1...an szó (a1,...,anV) hosszán a benne szereplő betűk számát értjük (multiplicitással), jelekkel:w∣ = n. Az üresszó bármely V ábécé esetén eleme a V*-nak, ∣λ∣ = 0.

A szavakat szokás sztringeknek is hívni. Két szó akkor egyenlő, ha hosszuk megegyezik és megfelelő helyen álló betűik is megegyeznek: u = v, ha ∣u∣ = ∣v∣ jelöljük ezt a hosszt n-nel, továbbá, ha n > 0 akkor u = a1...an, v = b1...bn (valamely ai,biV betűkre, 1 ≤ in) és ai = bi minden 1 ≤ in értékre. Röviden azt is mondhatjuk, hogy a képük, vagyis írásuk egyenlő.

A betűk és szavak közt értelmezett az összefűzésük, vagyis az egymásután írásuk, ennek a műveletnek a neve a konkatenáció (vagy szavak szorzása), jele a ⋅. Mivel a művelet eredménye éppen az a szó, amit a műveleti jel leírása nélkül kapunk, azt általában (ha nem kifejezetten kiemelni akarjuk) elhagyjuk. Az üresszó mindkétoldali egységeleme a műveletnek, vagyis bármely wV* esetén λ ⋅ w = w ⋅ λ = w. (Így λ ⋅ λ = λ.) A konkatenáció művelet asszociatív (vagyis u(vw) = (uv)w = uvw), de nem kommutatív (vagyis általában az uv és vu szavak nem feltétlenül egyenlőek).

Azt mondjuk, hogy a vV* a wV* szó kezdőszelete (prefixe), ha van olyan uV* szó, hogy w = v u. A v valódi kezdőszelete a w-nek, ha kezdőszelete és v ≠ λ, vw teljesül. Analóg módon értelmezzük a zárószelet fogalmát: Azt mondjuk, hogy a vV* a wV* szó zárószelete (végződése, suffixe), ha van olyan uV* szó, hogy w = uv. A u valódi suffixe a w-nek, ha zárószelete és v ≠ λ, vw teljesül. Végül, a vV* szó a wV* szó részszava (faktora), ha vannak olyan u1, u2V* szavak, hogy w = u1vu2. A v valódi részszava a w-nek, ha részszava és v ≠ λ, vw teljesül. Ahogy látjuk, a prefixek és suffixek a részszavak speciális esetei. Figyeljük meg, hogy λ részszava, prefixe és suffixe bármely ábécé feletti bármely szónak, de nem valódi prefixe/suffixe/részszava. Tehát a λ ott van minden szóban, az elején, a végén és bármelyik két betű közt, akárhányszor; viszont leírni csak akkor szoktuk, ha önmagában áll, vagy ki akarjuk emelni a szerepét.

15.1.2. Nyelvműveletek

A formális nyelvek tehát szavak halmazai, ennek megfelelően értelmezettek rajtuk a (kétargumentumú) halmazelméleti műveletek: unió, metszet, különbség, amelyeket rendre a ∪, ∩, és ∖ jelekkel jelölünk. Az unió és a metszet művelet is asszociatív és kommutatív. Adott V ábécé felett a V* tekinthető az univerzumnak, ennek megfelelően a(z egyargumentumú) komplementer művelet is értelmezett. (Figyeljük meg, hogy e művelet eredménye függ attól, milyen ábécé felett értelmeztük az adott nyelvet.) A nyelvekre is teljesülnek a De Morgan azonosságok:

és

illetve a disztributív azonosságok:

L1 ∩ (L2L3) = (L1L2) ∪ (L1L3),

valamint

L1 ∪ (L2L3) = (L1L2) ∩ (L1L3).

Az unió művelet egységeleme a {} üresnyelv, mely nem tartalmaz egyetlen szót sem. A metszet művelet egységeleme a V* nyelv, az univerzum.

A szavakon értelmezett konkatenációt kiterjeszthetjük a nyelvekre is. Legyen L1, L2V*, ekkor

L1L2 = {uvuL1, vL2}.

A nyelvek konkatenációja asszociatív, de nem kommutatív; mindkétoldali egységeleme a {λ} egységnyelv, amely egyetlen szót, az üresszót tartalmazza. Ezzel szemben

L ⋅ {} = {} ⋅ L = {}.

A nyelvek közti konkatenáció jelet sem írjuk ki mindig. A konkatenáció és az unió műveletekre teljesülnek a következő disztributív azonosságok:

L1 (L2L3) = (L1 L2) ∪ (L1 L3),

valamint

(L1L2) L3 = (L1 L3) ∪ (L2 L3).

Egy nyelv hatványait értelmezzük azzal, hogy saját magával konkatenáljuk:

  • L0 = {λ} (az egységnyelv)

  • ha i > 0, akkor Li = LLi-1.

Ennek megfelelően L1 = L és L2 = LL...

Szokás a Kleene-féle iteráció műveleteket definiálni a nyelvekre:

és

A Kleene-csillag és a Kleene-plusz műveletek eredménye pontosan akkor egyezik meg, ha L tartalmazza az üresszót. Ha λ ∉ L, akkor L*L+ = {λ} a két nyelv különbsége. Figyeljük meg, hogy L+ = L*L = LL*.

Szokás az unió, a konkatenáció és a Kleene-csillag műveleteket együttesen reguláris műveleteknek hívni, ezekre később még visszatérünk.

Most néhány további, a formális nyelvek elméletében szereplő alapdefiníciót, illetve jelölést mutatunk be.

15.1.3. Átíró és generatív rendszerek

22. Definíció. Formális rendszernek (vagy átíró-, esetleg átírási rendszernek) nevezünk minden olyan W = (V,H) párt, amelyben V egy ábécé, H pedig a V* × V* direkt szorzat egy véges részhalmaza. A H elemeit helyettesítési vagy átíró szabályoknak hívjuk, és ha (p,q) ∈ H, akkor általában a p → q jelölést használjuk.

Legyen r,sV*, akkor mondjuk, hogy r-ből az s közvetlenül, vagy egy lépésben levezethető (jelekkel: r ⇒ s), ha léteznek olyan p,p',p'',qV* szavak, hogy r = p'pp'', s = p'qp'' és p → qH. Szemléletesen ez azt jelenti, hogy az s szó megkapható az r szóból úgy, hogy s-ben valamely H-beli szabály bal oldalán álló p részszó helyébe az e szabály jobb oldalán álló q szót írjuk.

Azt mondjuk, hogy az r-ből az s levezethető (jelekkel: r ⇒* s), ha léteznek olyan r0,r1,...,rkV* szavak (k ≥ 1), hogy r0 = r és rk = s, valamint ri ⇒ ri+1 minden 0 ≤ i < k esetén. Emellett (a k = 0 esetnek megfelelően) r ⇒* r minden r szóra fennáll. (Tehát a ⇒* reláció a ⇒ reláció reflexív és tranzitív lezártja.)

A generatív rendszerekben egy adott – általában véges – axiómahalmazból levezethető szavak halmazát, a generált nyelvet vizsgáljuk. A klasszikus formális nyelvek elméletében a Chomsky által definiált generatív nyelvtanok és az általuk definiált nyelvosztályok alapvető szerepet játszanak. A generatív nyelvtanokban, szemben a korábbi egyszerű átírórendszerekkel, az ábécé elemeiből két diszjunkt csoportot, a terminálisok (kb. végleges betűk) és a nemterminálisok (kb. változók) halmazát képezzük. A fontosabb fogalmak a következők.

23. Definíció A G = (N, T, S, H) rendezett négyest generatív nyelvtannak (vagy generatív grammatikának) nevezzük, ha N és T diszjunkt véges ábécék, SN és H ⊂ (NT)*N(NT)* × (NT)*. Az N elemeit nemterminális jeleknek (változóknak) nevezzük, és általában nagybetűkkel jelöljük. A T elemeit terminális jeleknek (konstansoknak) nevezzük, és általában kisbetűkkel jelöljük. A H elemeit képező (p,q) rendezett párokat helyettesítési, vagy levezetési szabályoknak nevezzük, és általában itt is p → q alakban írjuk őket. Az S egy kitüntetett nemterminális jel, amely a nyelvtanban a generálás kiinduló vagy kezdő eleme, más néven mondatszimbóluma (startszava vagy axiómája).

Egy generatív nyelvtanban az r ∈ (NT)* szóból egy lépésben, vagy közvetlenül levezethető a t ∈ (NT)* szó (jelekkel: r ⇒ t), ha van olyan p → q helyettesítési szabály a H-ban és p',p'' ∈ (NT)* úgy, hogy r = p'pp'' és t = p'qp''. A levezethetőség definícióját ugyanúgy kapjuk a közvetlen levezethetőségből, mint az átíró rendszerek esetén, vagyis a közvetlen levezethetőség reflexív és tranzitív lezártjaként értelmezzük, jelekkel: ⇒*.

Az S mondatszimbólumból levezethető (NT)*-beli szavakat mondatformának hívjuk. A G generatív nyelvtan által generált nyelven a T*-beli S-ből levezethető szavak halmazát értjük:

L(G) = {wS ⇒* w} ∩ T*.

A nyelvtan és az általa generált nyelv definíciója szerint minden nyelvtanhoz egy egyértelműen meghatározott nyelv tartozik, de megfordítva, egy nyelvet nem csak egy nyelvtannal generálhatunk. Két nyelvtant ekvivalensnek nevezünk, ha ugyanazt a nyelvet generálják, vagy az általuk generált nyelv legfeljebb a λ üresszóban tér el.

A definícióból láthatjuk, hogy a központi szerepet játszó levezetés alapvetően szekvenciálisan, nemdeterminisztikusan működik, egy adott időpillanatban egy szabályt alkalmazunk az aktuális mondatforma egy adott helyén (ahol a szabály alkalmazható, azon helyek közül is csak egyetlen helyen).

15.1.4. A Chomsky hierarchia

A generatív nyelvtanokban a szabályok alakjának különböző megszorításával különböző típusú nyelvtanokat és azok által különböző típusú nyelvosztályokba tartozó nyelveket generálhatunk.

24. Definíció A G = (N, T, S, H)-t a következő kategóriákba soroljuk a benne szereplő levezetési szabályok alapján:

  • (0) Mondatszerkezetű nyelvtan: A generatív nyelvtan általános definíciója tejesül, ezen kívül nincs külön feltétel.

    (1') Monoton (szóhossznemcsökkentő) nyelvtan: Minden p → qH szabály eseténp∣ ≤ ∣q∣, ami alól egyetlen kivétel lehet: az S → λ alakú szabály, de ez esetben, vagyis S → λ ∈ H esetén S nem lép fel egyetlen szabály jobb oldalán sem.

  • (1) Környezetfüggő nyelvtan: Minden H-beli szabály alakja qAr → qpr, ahol AN, p ∈ (NT)* ∖ {λ}, q,r ∈ (NT)*; ez alól egyetlen kivétel lehet: az S → λ alakú szabály, de ez esetben, vagyis S → λ ∈ H esetén S nem lép fel egyetlen szabály jobb oldalán sem.

  • (2) Környezetfüggetlen nyelvtan: Minden szabály A → p alakú, ahol AN, p ∈ (NT)*.

  • (2.5) Lineáris nyelvtan: Minden egyes szabály A → uBv vagy A → u alakú, ahol A,BN, u,vT*.

  • (3) Reguláris nyelvtan: Minden egyes szabály vagy A → uB vagy A → u alakú, ahol A,BN, uT*.

Az i = 0,1,2,3 esetekben szokás a nyelvtant i-típusú nyelvtannak nevezni. Továbbá, egy nyelvről azt mondjuk, hogy rekurzívan felsorolható (RE, 0-típusú) / környezetfüggő (CS, 1-típusú) / környezetfüggetlen (CF, 2-típusú) / lineáris (LIN) / reguláris (REG, 3-típusú), ha mondatszerkezetű / környezetfüggő / környezetfüggetlen / lineáris / reguláris nyelvtannal generálható. Továbbá az i = 0,1,2,3 értékek esetén azt mondjuk, hogy egy L nyelv i-típusú, ha van olyan i-típusú nyelvtan, amely azt generálja. A monoton nyelvtanok által generált nyelvosztályt pedig jelölje, MON.

29. Tétel (Chomsky-féle hierarchia). A Chomsky féle nyelvosztályok az alábbi valódi hierarchiát alkotják adott legalább kétbetűs T ábécé felett:

FINREGLINCFCS = MONREALL,

ahol FIN jelzi a véges nyelvek halmazát és ALL jelzi az összes lehetséges nyelv halmazát.

Egybetűs T ábécé esetén

FINREG = LIN = CFCS = MONREALL.

Itt jegyezzük meg, hogy minden generatív nyelvtannal van olyan ekvivalens, amelyben a mondatszimbólum nem fordul elő egyik szabály jobb oldalán sem. Továbbá, az adott nyelvosztályok nyelvtanaiban szereplő szabályokra erősebb megszorításokat is tehetünk, úgy, hogy azért minden, a nyelvtanosztályba tartozó nyelvtannal van ekvivalens nyelvtan, melynek szabályaira ez az erősebb megszorítás is teljesül. Most néhány példát adunk erre.

15.1.5. Nyelvtanok normálformái

Ahogy korábban is említettük már, ekvivalensnek tartunk két nyelvtant, ha az általuk generált nyelvek legfeljebb a λ-ban különböznek; vagyis nem tartjuk lényegesnek e különbséget a két nyelv között. Ha csak a generált nyelv λ-mentes részére (L ∖ {λ}) korlátozzuk vizsgálatainkat, erős megszorításokat tehetünk a felhasználandó levezetési szabályokra. A megszorítások egy része a szabályok hosszának korlátozása, míg másik része pl. terminális bevezetésének szükségessége lehet, amint az alábbi esetekben látható.

  • Minden reguláris nyelv generálható olyan G = (N, T, S, H) nyelvtannal, amelynek szabályai csak

    A → aB, A → B, A → a, A → λ

    alakúak (A, BN, aT) lehetnek.

  • Továbbá minden egyes G = (N, T, S, H) reguláris nyelvtannal van olyan ekvivalens nyelvtan G' = (N', T, S,H') amelynek szabályai csak

    A → aB, A → a

    alakúak, ahol A, BN', aT.

  • Minden lineáris nyelv generálható olyan G = (N, T, S, H) nyelvtannal, amelynek szabályai csak

    A → aB, A → Ba, A → B, A → a, A → λ

    alakúak (A, BN, aT) lehetnek.

  • Továbbá minden egyes G = (N, T, S, H) lineáris nyelvtannal van olyan ekvivalens nyelvtan G' = (N', T, S, H') amelynek szabályai csak

    A → aB, A → Ba, A → a

    alakúak, ahol A, BN', aT.

  • Minden egyes G = (N, T, S, H) környezetfüggetlen nyelvtanhoz van vele ekvivalens G' = (N', T, S, H') nyelvtan, amelynek szabályai csak

    A → BC, A → a

    alakúak (A, B, CN', aT) lehetnek. Az ilyen megszorításokat teljesítő (környezetfüggetlen) nyelvtanokat Chomsky-féle normálformájúnak nevezzük.

  • Minden λ-mentes környezetfüggetlen nyelv generálható olyan G = (N, T, S, H) nyelvtannal, melynek minden egyes szabálya

    A → au

    alakú, ahol AN, aT, uN*. Az ilyen megszorításokat teljesítő (környezetfüggetlen) nyelvtanokat Greibach-normálformájúnak nevezzük.

  • Minden egyes monoton (és minden egyes környezetfüggő) G = (N, T, S, H) nyelvtanhoz van vele ekvivalens G' = (N', T, S', H') monoton nyelvtan, aminek szabályai csak

    AB → CD, A → BC, A → B, A → a

    alakúak (A, B, C, DN', aT) lehetnek. Az ilyen megszorításokat teljesítő nyelvtanokat Kuroda-normálformájúnak nevezzük.

  • Minden egyes környezetfüggő (és minden egyes monoton) G = (N, T, S, H) nyelvtanhoz van vele ekvivalens G' = (N', T, S', H') (monoton és egyben) környezetfüggő nyelvtan, aminek szabályai csak

    AB → AC, AB → CB, A → BC, A → B, A → a

    alakúak (A, B, CN', aT) lehetnek. Az ilyen megszorításokat teljesítő nyelvtanokat Révész-féle normálformájúnak nevezzük.

  • Minden egyes környezetfüggő (és minden egyes monoton) G = (N, T, S, H) nyelvtanhoz van vele ekvivalens G' = (N', T, S', H') környezetfüggő nyelvtan, aminek szabályai csak

    AB → AC, A → BC, A → a

    alakúak (A, B, CN', aT) lehetnek. Az ilyen megszorításokat teljesítő nyelvtanokat Penttonen-féle (egyoldali) normálformájúnak nevezzük.

  • Minden rekurzívan felsorolható nyelv előállítható monoton és A → λ alakú törlő szabályok segítségével, így a törlő szabályokkal kiegészítve a monoton, illetve környezetfüggő nyelvekre definiált normálformákat kapjuk a rekurzívan felsorolható nyelvekre vonatkozó megfelelő (pl. Kuroda, Penttonen) normálformát.

  • Minden rekurzívan felsorolható nyelv előállítható olyan nyelvtannal, amiben {S, A, B, C, D} öt nemterminális szerepel és aminek minden egyes szabálya

    SuSv, Su, AB → λ, CD → λ

    alakúak (ahol u, v ∈ (T ∪ {A, B, C, D})*). A csak ilyen alakú szabályokat tartalmazó nyelvtant Geffert-féle normálformának nevezzük.

15.1.6. Nyelvosztályok tulajdonságai

A reguláris nyelvek egy alternatív definíciója a reguláris kifejezésekkel történik.

25. Definíció. Legyen T = {a1,...,an} ábécé. Ha kibővítjük a benne nem szereplő ∅, λ, +, ⋅, *, ( és ) jelekkel, V = T ∪ {∅, λ, +, ⋅, *, (,)}, akkor V felett a következő iteratív módon definiáljuk a reguláris kifejezéseket:

  • Elemi kifejezések

    • egy reguláris kifejezés, ami az {} üres nyelvet írja le;

    • λ egy reguláris kifejezés, ami az {λ} egységnyelvet írja le;

    • a egy reguláris kifejezés, minden aT-re, és az {a} nyelvet írja le (amiben egy szó van, és az is egybetűs).

  • Indukciós lépések:

    • ha p,r reguláris kifejezések, amik az Lp és Lr nyelveket írják le, akkor (p+r) is reguláris kifejezés, és az LpLr nyelvet írja le;

    • ha p,r reguláris kifejezések, amik az Lp és Lr nyelveket írják le, akkor (pr) is reguláris kifejezés, és az LpLr nyelvet írja le;

    • ha r reguláris kifejezés, ami az Lr nyelveket írja le, akkor r* is reguláris kifejezés, és az nyelvet írja le.

A zárójelek egy részét el szokás hagyni, köszönhetően pl. az unió és a konkatenáció asszociativitásának, illetve a szokásos precedenciának: a * (egyargumentumú művelet) a legerősebb, aztán a konkatenáció (szorzás), és az unió (összeadás) a leggyengébb.

Köztudott, hogy éppen a Chomsky-féle 3-típusú nyelvek (vagyis REG) írhatóak le reguláris kifejezésekkel. Az unió, a konkatenáció és az iteráció műveleteket reguláris műveleteknek hívjuk.

Azt mondjuk, hogy egy nyelvosztály zárt egy adott műveletre nézve, ha a nyelvosztály bármely nyelveiből a művelet eredményeként olyan nyelvet kapunk, amely ugyancsak a nyelvosztály eleme. Az alapvető nyelvosztályok fontos műveletekre vett zártsági tulajdonságait a 15.1. táblázat tartalmazza (+ jelenti a zárt és - a nem zárt tulajdonságot az adott műveletre nézve).

15.1. táblázat - A Chomsky-féle nyelvosztályok zártsági tulajdonságai.

nyelvosztályművelet
uniókonkatenációKleene-iterációmetszetkomplementer
reguláris+++++
lineáris+----
környezetfüggetlen+++--
környezetfüggő+++++
rekurzívan felsorolható++++-

A Chomsky-féle 0., 1., 2. és 3. nyelvosztály is zárt az unió, a nyelvek összefűzése (konkatenáció), illetve az iteráció műveletére is. A lineáris nyelvek osztálya zárt az unió, de nem zárt a konkatenáció és az iteráció műveletekre. A reguláris és a környezetfüggő nyelvek zártak a metszet és a komplementerképzés műveletekre, a lineáris és a környezetfüggetlen nyelvek osztálya pedig nem zárt ezekre a műveletekre. Amennyiben viszont az egyik nyelv környezetfüggetlen, a másik reguláris, a metszetük is környezetfüggetlen lesz, vagyis a környezetfüggetlen nyelvek zártak a reguláris nyelvekkel vett metszetképzésre. A rekurzívan felsorolható nyelvek osztálya zárt a metszet, de nem zárt a komplementerképzés műveletére.

A következő nyelvek híres nem környezetfüggetlen, környezetfüggő nyelvek:

  • {w ww ∈ {a,b}*} a másolat nyelv, illetve a {wcww ∈ {a,b}*} a jelölt másolat nyelv;

  • {anbncnn ∈ ℕ} a többszörös megfelelés nyelve;

  • {anbmcndmn, m ∈ ℕ} a keresztfüggőségek nyelve.

Egy V = {a1, ..., an} rendezett ábécé felett adott w szó Parikh vektorát definiáljuk a következőképpen: Φ(w) = (∣wai) egy n-dimenziós vektor, ahol aiV és w az ábécé i. betűjét pontosan ∣wai-szer tartalmazza. Egymás kommutatív képeinek, vagy betűekvivalensnek nevezünk két szót, ha a betűik sorrendjének átrendezésével az egyikből a másikat előállíthatjuk. A betűekvivalens szavak Parikh vektora megegyezik. A w szó kommutatív képeinek halmaza jellemezhető a Parikh vektorral, mintha a sztringekben a betűk sorrendje nem számítana: így multihalmaz adatszerkezettel írhatjuk le őket: ezt jelentik a Parikh vektorok. Adott L nyelv, az L nyelv Parikh halmazát a következőképpen definiáljuk: Φ(L) = {Φ(w) ∣ wL}. Egy nyelv Parikh halmaza tehát a nyelv szavainak Parikh vektorait tartalmazó halmaz.

Két ugyanazon rendezett ábécé felett értelmezett nyelvet betűekvivalensnek nevezünk, ha Parikh halmazaik megegyeznek. Ekkor a két nyelv bármelyikében találunk a másik minden egyes w szavához olyan w' szót, hogy w és w' legfeljebb a betűk sorrendjében tér el.

Legyen az ábécénk számossága n. Egy nyelvet (Parikh értelemben) lineárisnak nevezünk, ha Parikh halmaza lineáris, vagyis teljesül rá a következő feltétel: van k + 1 darab olyan n-dimenziós vektor (v0, ..., vk), hogy

Egy L nyelv szemilineáris, ha Parikh halmaza lineáris halmazok véges uniója.

Minden környezetfüggetlen (vagyis CF) nyelv szemilineáris (Parikh-tétele). Továbbá ismert, hogy minden szemilineáris nyelvhez van vele betűekvivalens reguláris nyelv. Ráadásul, az egybetűs ábécé felett a szemilineáris nyelvek éppen megegyeznek a reguláris, a lineáris, illetve a környezetfüggetlen nyelvek osztályával.

Vannak olyan környezetfüggő nyelvek, amik nem szemilineárisak, pl. a

  • {an2n ∈ ℕ}, a négyzethosszú szavak nyelve;

  • {a2nn ∈ ℕ} a kettő-hatvány hosszú szavak nyelve; vagy

  • {app prímszám} a prímszámok (prímszámhosszú szavak) nyelve.