Shape Grammars and their Uses: Artificial Perception, Shape Generation and Computer Aesthetics

گرامرهای شکل وسیله ای برای مشخص کردن بازگشتی اشکال فراهم می کنند. فرمالیسم برای گرامرهای شکلی به گونه ای طراحی شده است که برای افراد به راحتی قابل استفاده و قابل درک باشد و در عین حال برای استفاده در برنامه های کامپیوتری قابل انطباق باشد. گرامرهای شکلی شبیه گرامرهای ساختار عبارت هستند که توسط چامسکی [1956، 1957] توسعه یافتند. در جایی که یک دستور structura عبارت بر روی الفبای نمادها تعریف می شود و زبانی از دنباله نمادها را ایجاد می کند، یک گرامر شکل بر روی الفبای اشکال تعریف می شود و زبانی از اشکال را ایجاد می کند. این پایان نامه به بررسی کاربردهای گرامر شکل می پردازد. پایان نامه به سه بخش و یک پیوست تقسیم شده است. در بخش اول: گرامرهای شکل تعریف شده است. چند مثال ساده برای اهداف آموزشی آورده شده است. از گرامرهای شکل برای تولید دسته جدیدی از اشکال برگشت پذیر استفاده می شود. گرامرهای شکل برای برخی از منحنی های ریاضی شناخته شده (منحنی برف ریزه، تغییری از منحنی Peano و منحنی هیلبرت) ارائه شده است. برای نشان دادن قدرت محاسباتی کلی گرامرهای شکل، رویه‌ای ارائه می‌شود که با توجه به هر ماشین تورینگ، گرامر شکلی را می‌سازد که عملکرد آن ماشین تورینگ را شبیه‌سازی می‌کند. کارهای مرتبط بر روی فرمالیسم های مختلف برای گرامرهای تصویری شرح داده شده است. یک توصیف نمادین از گرامرهای شکل ارائه شده است که برای پیاده سازی گرامرهای شکل در برنامه های کامپیوتری مفید است.

Shape grammars provide a means for the recursive specification of shapes. The formalism for shape grammars is designed to be easily usable and understandable by people and at the same time to be adaptable for use in computer programs. Shape grammars are similar to phrase structura grammars, which were developed by Chomsky [ 1956, 1957]. Where a phrase structura grammar is defined over an alphabet of symbols and generates a language of sequences of symbols, a shape grammar is defined over an alphabet of shapes and generates a language of shapes. This dissertation explores the uses of shape grammars. The dissertation is divided into three sections and an appendix. In the first section: Shape grammars are defined. Some simple examples are given for instructiva purposes. Shape grammars are used to generate a new class of reversible figures. Shape grammars are given for some well-known mathematical curves (the Snowflake curve, a variation of Peano's curve, and Hilbert's curve). To show the general computational power of shape grammars, a procedura that given any Turing machine constructs a shape grammar that simulates the operation of that Turing machine is presented. Related work on various formalisms for pictura grammars is described. A symbolic characterization of shape grammars is given that is useful for implementing shape grammars in computer programs.