3.3. L-rendszerek

A Markov-féle normál algoritmus esetén minden lehetséges lépésben egyértelműen meg volt fogalmazva, hogy melyik szabályt és hol kell alkalmazni (illetve, ha kiszámoltuk a megoldást, és nem folytatódik a számítás). Ezzel szemben a generatív nyelvtanoknál sem az hogy melyik szabályt (több alkalmazható is lehet egyszerre), sem az hogy hol (egy adott szabály az aktuális mondatforma több helyén is alkalmazható lehet ugyanakkor) kell alkalmazni nincs egyértelműen megadva, vagyis a nyelvtanok nemdeterminisztikusak. Viszont minden eddigi korábban ismertetett rendszerre teljesült, hogy minden időpillanatban pontosan egy szabályt pontosan egy helyen alkalmaztunk, vagyis az eddig tárgyalt rendszerek szekvenciális működésűek. Ebben a fejezetben egy olyan modellt vizsgálunk meg, amely alapvetően párhuzamos.

Aristid Lindenmayer (1925-1989), a Fasori Gimnáziumba (Budapesti Evangélikus Gimnázium) járt, hasonlóan több magyar Nobel-díjashoz (pl. Wigner Jenő), vagy Neumann Jánoshoz. Később Hollandiában tevékenykedő biológusként először bizonyos algafajok növekedési mintázatainak leírására alkalmazott formális rendszereket, majd ezeket a matematikai eszközöket magasabb szintű növények fraktálszerkezetének leírására alkalmazták.

5. Definíció. Egy L-rendszer (Lindenmayer-system, L-system) egy párhuzamos átíró rendszer L S=(T, s, H), ahol T egy véges ábécé, sT * (axióma), H pedig a → r alakú (aT, rT *) átíró szabályok halmaza.

Az alap L-rendszerekben minden aT betűhöz pontosan egy átíró szabály (esetleg a → a alakú) létezik. Egy levezetési lépésben az adott mondatforma/szó (axióma) minden betűjét helyettesítjük a megadott átírási szabályok alapján, így létrehozva a következő mondatformát/szót.

Az LS rendszer által generált nyelv tartalmazza az összes olyan szót (beleértve az axiómát is) amely véges sok lépésben generálható az axiómából.

3.37. példa - Fibonacci szavak

Legyen ({a, b}, a, {a → b, bb a}) L-rendszer. Ekkor könnyen ellenőrizhető, hogy az ezzel a rendszerrel generált nyelv első néhány szava: a, b, b a, b a b, b a b b a, b a b b a b a b, … Ez a Fibonacci szavak nyelve.


Figyeljük meg, hogy az egymást követő szavak hosszai éppen a Fibonacci számok (az f(0)=1, f(1)=1, f(i)=f(i-1)+f(i-2), (i>1- re) rekurzív képlettel definiált sorozat). Másrészt a szavak felépítése is hasonlít a számsorozatot előállító képlet alkalmazására: w(0)=a, w(1)=b, w(i)=w(i-1)w(i-2) . ★

3.38. példa - Fraktálgenerálás L-rendszerrel

A Cantor-halmaz egyike a jól ismert fraktáloknak, ennek egy előállítása történhet a következő L-rendszer segítségével: ({0,1}, 1, {1 → 101, 0  → 000}).


A generálás folyamata: 1, 101, 101000101, 101000101000000000101000101 jobban követhető a következő képen, ahol 1 jelzi a szakaszokat, 0 pedig azok hiányát:

A levezetést a végtelenségig folytatva (határsetben) megkapjuk a Cantor által definiált fraktált. ★

Növények formáját, hasonlóan, néhány egyszerű átíró szabállyal tudjuk kódolni, valószínűleg a természet is hasonlóképpen kódolja a kifejlett növény felépítését a növény génállományában. A következőkben egy egyszerű ilyen jellegű példát mutatunk.

3.39. példa - Kétdimenziós rajz L-rendszerrel

({},,H), ahol a H szabályhalmaz elemei:

; ;

A generálás első néhány lépése:


Természetesen rengeteg változata van az L-rendszereknek, itt csak a legalapvetőbb változatot ismertettük röviden.