L-System

به نام خداL-Systemمحمد یوسفیان، تینا محمدی ، عرفان آجورلو مقدمه :‌در سال ۱۹۶۸ ، یک گیاه شناس مجار به نام Aristid Lindenmayer یک سیستم گرامری جهت مدل کردن الگو های رشد گیاهان ارائه ‌داد . این سیستم را L-System می نامیم. L-System به طور کل در مطالعه و مدل کردن شکل شناسی ارگانیسم های مختلف کاربرد دارد . در اصل ، L-System ساختاری را بر پایه رشته ها فراهم می کند که با این ساختار کار های مختلفی در زمینه های گرافیک کامپیوتری ، تولید موسیقی ، تولید فراکتال های self-similar ، شبیه سازی رشد سلول ها و گیاهان و ... انجام داد تعریف :فرض کنیم G یک L-System باشد . G را به این صورت تعریف می کنیم :

\begin{array}{l} W = (V, 𝜔, P) \\ V : s e t o f v a r i a b l e s a n d t e r m i n a l s \\ 𝜔 : a x i o m \\ P : s e t o f a l l t h e r u l e s l i k e R : V \to V^{*} \end{array}

𝜔

را axiom نامیم و متغیری آغازین L-System است فرض می شود که برای هر

x \in V

، وجود دارد

y \in V^{*}

به طوری که

x \to y

x

را predecessor و

y

را successor می نامیم. اگر برای predecessor ای مانند

a \in V

قاعده ای به طور صریح وجود نداشته باشد ،

a \to a

فرض می شود (identity rule ) در L-System به ازای هر کاراکتری که در رشته داریم ، اگر قاعده none-identity ای وجود داشته باشد ، باید آن را اعمال کنیم . همین قضیه باعث تفاوت بین L-System ها و formal-grammer ها می شود. برای مثال فرض کنید که گرامری داریم که دارای قاعده زیر است :

S \to S S

اگر این قاعده مربوط به یک formal-grammer باشد ، در اثر اعمال قاعده خواهیم داشت :‌

S \Rightarrow S S \Rightarrow S S S \Rightarrow S S S S \Rightarrow S S S S S \Rightarrow . . .

در حالی اگر این قاعده مربوط به یک L-System باشد خواهیم داشت:

S \Rightarrow S S \Rightarrow S S S S \Rightarrow S S S S S S S S \Rightarrow S S S S S S S S S S S S S S S S \Rightarrow . . .

واضح است که با متغیر ها و ترمینال ها و متغیر آغاز و قواعد یکسان ، زبان تولید شده توسط یک L-System زیرمجموعه زبان تولید شده توسط formal-grammer است . تعریف context-free L-System : یک L-system مستقل از متن است اگر L سیستم را محدود کنیم به این که هر قاعده ای فقط در یک کاراکتر فقط اثر کند و در کاراکتر های دیگر اثر نکند . پس L-System های مستقل از متن توسط گرامر های مستقل از متن شناسایی می شوند. تفاوت L-System با گرامر چامسکی :‌ در گرامر چامسکی متغیر ها جدا از ترمینال ها هستند و هر کدام جدا تعریف می شوند.ولی در ‍ L-System متغیر ها و ترمینال جدا تعریف نمی شوند. طبق تعریف L-System ،‌برای هر ترمینالی مانند

a

قاعده

a \to a

وجود دارد ، در حالی که در گرامر چامسکی نمی توان این قاعده را برای یک ترمینال تعریف کرد. کاربرد ها و مثال ها : برای مشاهده مثال ها به این لینک مراجعه کنید . همچنین کد های پروژه را می توانید در این لینک مشاهده کنید. منابع : ویکی پدیای انگلیسی کتاب Nature Of Code . نویسنده : Daniel Shiffman کتاب The Computational Beauty of Nature . نویسنده :‌ Gary William Flake کانال یوتیوب The Coding Train

بازگشت به صفحه اصلی