نظریه زبانها و ماشینها

این وبلاگ به منظور توفیق روزافزون در فراگیری درس نظریه زبان می باشد

آزمون تورینگ

در سال ۱۹۵۰ آلن تورینگ، ریاضیدان انگلیسی، معیار سنجش هوشمندی یک ماشین را چنین بیان داشت:

«سزاوارترین معیار برای هوشمند شمردن یک ماشین، اینست که آن ماشین بتواند انسانی را توسط یک پایانه تله تایپ به گونه‌ای بفریبد که آن فرد متقاعد گردد با یک انسان روبروست.»

در این آزمایش شخصی از طریق ۲ عدد پایانه (رایانه یا تله تایپ) که امکان برقراری ارتباط و گپ‌زنی را برای وی فراهم می‌کنند با یک انسان و یک ماشین هوشمند، بطور هم‌زمان به پرسش و پاسخ می‌پردازد. در صورتی که وی نتواند ماشین را از انسان تشخیص دهد، آن ماشین، هوشمند است. خلاصه ابنکه مورد تحقیق قرار گیرد و محقق نتواند دریابد در آن طرف انسان قرار دارد یا کامپیوتر.

آزمایش تورینگ از قرار دادن انسان و ماشینید، از تفکری انسانی برخوردار است.

آزمایش تورینگ مدل سازی نحوه تفکر انسان، تنها راه تولید ماشینهای هوشمند نیست. هم اکنون دو هدف برای تولید ماشینهای هوشمند، متصور است، که تنها یکی از آن دو از الگوی انسانی جهت فکر کردن بهره می‌برد:

  • سیستمی که مانند انسان فکر کند. این سیستم با مدل کردن مغز انسان و نحوه اندیشیدن انسان تولید خواهد شد و بنابراين از آزمون تورینگ سر بلند بیرون می‌آید. از این سیستم ممکن است اعمال انسانی سر بزند.

تا به امروز هیچ نرم‌افزار یا ماشین هوشمندی نتوانسته است از این آزمون سربلند بیرون بیاید.


ادامه مطلب
+ نوشته شده در  دوشنبه چهارم تیر 1386ساعت 10:5  توسط automata83shahed  | 

لینک های ارسالی در زمینه نظریه زبان

لینک مطالب ارسالی خانم مرجان اردویی:

http://rapidshare.com/files/38464062/orduyi.rar.html

و لینک مطالب خانم اکرم هاشمی:

http://rapidshare.com/files/38464755/hashemi.rar.html

همچنین لینک مطالب خانم بیگی محمدی:

http://rapidshare.com/files/38465268/beigi.rar.html 

هر لینک شامل فایل های نمونه سوال و لینک های دیگر است.

لطفا تا قبل از ۵/۴/۸۶ مطالب خود را ارسال کنید.

با تشکر

+ نوشته شده در  پنجشنبه سی و یکم خرداد 1386ساعت 11:18  توسط automata83shahed  | 

نمونه سوال نظریه زبان ها

لینک فایل فشرده نمونه سوال نظریه زبان ها:

http://rapidshare.com/files/38463276/khatami.rar.html

ارسال کننده:ملیحه خاتمی

+ نوشته شده در  پنجشنبه سی و یکم خرداد 1386ساعت 10:58  توسط automata83shahed  | 

نمونه سوالات نظریه زبان ها

لینک یک نمونه سوال از درس نظریه که توسط خانم الهه عباسپور ارسال شده است:

http://rapidshare.com/files/38364399/automata.doc.html

 

+ نوشته شده در  چهارشنبه سی ام خرداد 1386ساعت 21:23  توسط automata83shahed  | 

نمونه سوالات نظریه زبان ها

چند نمونه سوال از درس نظریه زبان به همراه جواب آن ها:

http://rapidshare.com/files/38257630/nazarieh.rar.html

ارسال کننده :منیژه جباری

+ نوشته شده در  چهارشنبه سی ام خرداد 1386ساعت 9:5  توسط automata83shahed  | 

ساده کردن DFA

https://www.sharemation.com/radsoli/1.doc?uniq=23fvts

 

 

 

امیر فتوحی

+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:53  توسط automata83shahed  | 

زبان های بازگشتی

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی یک نوع زبان صوری است که همچنین بازگشتی، تصمیم پذیر یا تصمیم پذیر بازگشتی نامیده می شود.کلاس تمامی زبان های بازگشتی غالبا" R نامیده می شود، با اینکه این نام برای کلاس RP نیز استفاده می شود.

این نوع از زبان به طور واضحی از سلسله مراتب چامسکی(Chomsky hierarchy) جا مانده است.

تعاریف:

دو تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:

1-  یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی(recursive subset)در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.

2-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با یک رشته ورودی مواجه می گردد، متوقف می شود و اگر رشته در زبان موجود  باشد آن را می پذیرد، در غیر این صورت متوقف می گردد و آن رشته را نمی پذیرد. ماشین تورینگ همیشه متوقف می گردد: این ماشین به عنوان تصمیم پذیر شناخته می شود. 

 تمامی زبان های بازگشتی بازگشتی برشمردنی نیز هستند. تمامی زبان های منظم، مستقل از متن وحساس به متن زبان های بازگشتی می باشند.

خواص بسته بودن:

زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:

- ستاره L

- اتصال L وP

- اجتماع L وP

- اشتراک L وP

- اختلاف L وP

امیر فتوحی
+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:48  توسط automata83shahed  | 

بسمه تعالی

تز تورینگ

نظریه زبانها – ماشین تورینگ

تر جمه The Church Turing Thesis  

    به دنبال توسعه نظریه محاسبات، چندین مدل از ابزارهای محاسباتی را ارائه می کنیم. آتاماتای متناهی، مدلهای خوبی برای ابزارهای با جافظه کوچک هستند. آتاماتای push down ، مدلهای خوبی برای ابزارهای با حافظه نامحدود هستند که فقط به روش last in first out یا همان LIFO که روش حافظه پشته (stack) است مورد استفاده قرار می گیرند. ما نشان می دهیم که برخی وظایف خیلی ساده  فراتر از قابلیتهای این مدلهاست. ازینرو ، آنها خیلی محدود می شوند تا بتوانند بعنوان مدلهایی از کامپیوترهای همه منظوره  عمل کنند.

    اکنون سراغ مدل خیلی قویتری می رویم که نخستین بار توسط آلن تورینگ (Alan Turing) در سال 1936 میلادی و تحت عنوان ماشین تورینگ ارائه شد. مشابه یک آتاماتای محدود ولی با حافظه ای نامحدود و بدون شرط است و مدل دقیقتری از یک کامپیوتر همه منظوره را ارائه می کند. یک ماشین تورینگ تمام کارهایی که یک کامپیوتر همه منظوره انجام می دهد را انجام می دهد. اما با این وجود، ماشین تورینگ نیز از حل مسائل قطعی عاجز است. در یک نگاه خیلی دقیق، اینگونه مسائل فراتر از محدودیتهای تئوریک در محاسبات هستند.

    مدل ماشین تورینگ از یک نوار نامحدود بعنوان حافظه نامحدود خود استفاده می کند. این حافظه امکان خواندن و نوشتن سمبل ها  را دارد  و دور نوار می گردد. در ابتدا، نوار فقط حاوی رشته ورودی است و سایر مکان های آن خالی است. اگر ماشین نیازمند ذخیره کردن چیزی بود ، باید آنرا روی نوار ذخیره نماید. ماشین به کارش ادامه می دهد تا وقتی که بخواهد خروجی تولید کند. خروجی های قبول کردن یا ردکردن با تعیین حالات قبولی و ردی مشخص می شود. اگر چنین حالاتی ، تعریف نشوند  ماشین همواره و برای همیشه کار خواهد مرد و هرگز متوقف نخواهد شد.

    جهار مورد زیر، تفاوت های اساسی میان ماشین های تورینگ و آتاماتای متناهی است :

1-             یک ماشین تورینگ هم می تواند روی نوار بخواند و هم بنویسد.

2-              هد (head) خواندن و نوشتن می تواند هم به راست و هم به چپ حرکت کند.

3-              نوار، نامحدود است.

4-              حالات ویژه برای پذیرفتن یا رد کردن آثاری فوری دارد.

 

    به طور غیر رسمی، الگوریتم را اینگونه تعریف می کنیم که مجموعه ساده ای از دستورات ساده برای اجرای برخی وظایف است. الگوریتمها در زندگی روزمره و در ریاضیات نقش بسیاری دارند. اما بطور دقیقتر می توان این فهم شهودی از الگوریتمها را با نظریه ماشین تورینگ ، نشان داد. تاریخچه این امر، به ماجرای مهمی به نام مسائل هیلبرت باز می گردد.           

 

امیر فتوحی
+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:46  توسط automata83shahed  | 

سعيد جواني

زبان های صوری

 

در ریاضیات، منطق و علوم کامپوتر، زبان صوری یک مجموعه از کلمات (رشته های کاراکتری) با طول متناهی  است که از برخی الفباهای متناهی مشتق می گردد، و نظریه علمی که مرتبط با این مفاهیم است  به عنوان نظریه زبان صوری شناخته می شود.

یک الفبا ممکن است {a,b} ،و رشته بر روی آن ababba باشد.یک زبان نمونه بر روی این الفبا، که دارای رشته عنوان شده است، ممکن است مجموعه تمام رشته های باشد که شامل علائم a و b با تعداد مساوی است.

رشته تهی (رشتهای با طول صفر) رشته با معنا تلقی می گردد و با علامe, ε, Λ. نمایش داده می شود. از آن جایی که الفبا یک مجموعه متناهی است وهر عبارت دارای طول محدود است، زبان ممکن است دارای رشته های عضو نامحدود باشد.

سوالی که اغلب در مورد زبان های صوری پرسیده می شود این است "  آیا یک عبارت داده شده به زبان تعلق دارد یا خیر؟" ، که جواب آن، بحث مورد برسی نظریه محاسبات و نظریه پیچیدگی است

چند مثال از زبان های صوری:

1-     مجموعه رشته های تولید شده بر روی a و b .

2-     مجموعه {a^n}،n یک عدد اول است.

3-     زبانی متناهی مانند a،aa،bba .

4-     مجموعای از برنامه های یک زبان برنامه نویسی که از نظر نحوی صحیح می باشند.

5-     مجموعای از ورودی ها که ماشین تورینگ خاصی بر روی آن متوقف می گردد.

یک زبان صوری به وسیله راه های مختلفی مشخص می گردد، از جمله:

1-     رشته هایی که توسط گرام های صوری تولید می شوند.

2-     رشته هایی که توسط عبارات منظم تولید می شوند

3-     رشته هایی که توسط برخی ماشین ها، مانند ماشین تورینگ یا ماشین حالت متناهی پذیرفته می شوند.

4-     آن دسته از سوالات بله/ خیر که جوابشان بله است.

 

+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:41  توسط automata83shahed  | 

سعيد جواني

زبان های بازگشتی برشمردنی

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی برشمردنی یک نوع زبان صوری است که تا حدی تصمیم پذیر یا تصمیم پذیر تورینگ نیز نامیده می شود.این نوع زبان در سلسله مراتب زبان های صوری چامسکی با عنوان زبان نوع صفر شناخته می گردد.کلاس زبان های بازگشتی برشمردنی RE نامیده می شود.

تعاریف:

سه تعریف برابر و اصلی برای مفهوم زبان بازگشتی وجود دارد:

1-  یک زبان صوری بازگشتی یک زیر مجموعه بازگشتی( recursively enumerable subset ) در مجموعه تمامی کلمات ممکن بر روی الفبای زبان است.

2-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی(یا تابع قابل محاسبه دیگری)  وجود دارد که تمامی رشته های معتبر زبان راشمارش می کند. توجه داشته باشید که اگر زبان نا متناهی باشد، از آن جائیکه میتوانیم بررسی کنیم که آیا رشته تولید شده برای عدد n ، قبلا" برای عددی کوچکتر از n تولید شده یا نه، الگوریتم شمارش کننده می تواند به گونه ای انتخاب گردد که از تکرار جلوگیری کند. اگر رشته قبلا" تولید شده بود به جای ورودی n+1 از خروجی استفاده کنید(به صورت باز گشتی) ،اما مجددا" بررسی کنید که آیا جدید است یا نه.

3-  یک زبان بازگشتی یک زبان صوری است که برایش ماشین تورینگی وجود دارد که، هنگامی که با هر رشته ورودی موجود در زبان مواجه می گردد، متوقف می شود و  رشته  را می پذیرد، ماشین تورینگ مورد بحث هنگام مواجه با رشته ای که در داخل زبان نیست ممکن است متوقف شود و رشته را نپذیرد یا برای همیشه در حلقه بیا فتد.

تمامی زبان های منظم، مستقل از متن، حساس به متن و بازگشتی، بازگشتی برشمردنی هستند.

RE و مکملش (co-RE)  پایه سلسله مراتب حسابی (arithmetical hierarchy ) را تشکیل می دهند.

خواص بسته بودن:

زبان های بازگشتی برروی اعمال زیر بسته اند.یعنی، اگر زبان L و زبان P هر دو بازگشتی باشند، در نتیجه زبان های زیر نیز بازگشتی اند:

- ستاره L

- اتصال L وP

- اجتماع L وP

- اشتراک L وP

توجه کنید که زبان های بازگشتی برشمردنی بر روی اعمال مکمل گیری و تفاضل بسته نیستند.

+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:38  توسط automata83shahed  | 

سعيد جواني 832161015


 

ماشین تورینگ و مقایسه آن با ماشین واقعی

 Universal Turing machines( UTM )

هر ماشین تورینگ یک تابع ثابت  جزئی قابل محاسبه معین[1] را از روی رشته ورودی الفبایش محاسبه می کند. از این جهت مانند یک کامپیوتر با یک برنامه ثابت رفتار می کند. بهر حال ما قادریم که جدول عملیات [2] هر ماشین تورینگی را در یک رشته[3] کدگذاری[4] کنیم. بنابراین می توانیم یک ماشین تورینگ را که درانتظار یک رشته شرح دهنده ی جدول عملیات و بدنبالش یک رشته شرح دهنده نوار ورودی است را ایجاد کنیم , تا  نواری که ماشین تورینگ کدشده محاسبه می نمود را محاسبه نماید بعبارت دیگر جدول عملیات یک ماشین تورینگ  را به صورت یک  رشته ورودی به یک ماشین تورینگ  دیگر داده ایم تا محاسباتی که ماشین اول می بایست انجام می داد را ماشین مقصد انجام دهد. آقای تورینگ چنین ساختاری را با جزئیات بیشتر در مقاله ای در سال 1936 شرح داد.

در 1937 , وی چنین اظهار نمود:

"می توان نشان داد که یک ماشین خاص منفرد از این نوع را می توان ساخت که بتواند کار همه ماشینها را انجام دهد.در حقیقت می توان چنین ماشینی ساخت تا بصورت یک مدل برای هر ماشین دیگری کار کند , این ماشین خاص را ماشین جهانی[5] می نامیم . "

این گفته ,شاید , اولین نظریه مقدماتی  برای سیستم عامل باشد؛ یک برنامه برای اجرای کنترل شده برنامه های دیگر . . . نشان داد که چنین ماشینی وجود دارد – واینرا که می توان بصورت عملی چنین مدلی داشت را برای اذهان قابل قبول کرد.

با چنین کدکردن جداول عملیاتی بصورت رشته های ورودی , بعنوان یک اصل برای ماشینهای تورینگ  ممکن شد که به سوالاتی درباره رفتار ماشینهای تورینگ دیگر پاسخ دهند. بسیاری از این پرسشها , اگرچه تصمیم ناپذیرند[6], بدین معنی که تابع مورد سوال بصورت مکانیکی قابل محاسبه نیست. بعنوان مثال , مسئله  اینکه :" آیا  یک ماشین تورینگ مشخص  برای یک ورودی خاص  , یا برای همه ورودیها توقف[7] خواهد نمود؟" , که با عنوان" مسئله توقف[8] " مشهور است , نشان داده شده که بطور کلی در مقاله اصلی تورینگ تصمیم ناپذیر است . قضیه Rice   نشان می دهد که هر سوال غیر بدیهی در باره رفتار یا خروجی یک ماشین تورینگ تصمیم ناپذیر است .

یک  UTM  می تواند نسبتا ساده باشد ,  فقط شامل تعداد  کمی حالات و نیز تعداد معدودی از Symbol ها .بعنوان مثال از وقتی که یک   2X18 UTM (به معنی دو حالت و 18 Symbol ) شناخته شده است  فقط دو حالت (State ) مورد نیاز است .

گاهی اوقات کوچکترین UTM های شناخته شده که یک مدل محاسباتی بنام سیستم برچسب[9]  را شبیه سازی کرده اند دارای این تعداد از حالات و Symbol ها بوده اند:

2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 24×2 (بعنوان نمونه برای توضیحات مفصل یک  ماشین tag-system-based 4x7    ببینید : Minsky , بخش : 14.8.1 صفحه (  277

Wolfram در کتاب خود " "A New Kind of Scienceیک UTM کوچکتر با 2 حالت و 5 Symbol معرفی کرد که یک اوتوماسیون سلولی[10] را شبیه سازی می کند که آنرا بعنوان ساده ترین UTM  شناخته شده  در آورد.

یک ماشین تورینگ جهانی Turing-complete  می باشد . چنین ماشینی قادر است که هر تایع بازگشتی را محاسبه کند , هر زبان بازگشتی را استنتاج نماید و هر زبان بازگشتی قابل شمارش[11] را بپذیرد. برمبنای قضیه Church-Turing مسائلی که با UTM قابل حل اند کاملا با یک الگوریتم ویا با یک متود محاسباتی موثر[12] قابل حل خواهند بود .

یک نسخه مجرد[13]  از ماشین تورینگ جهانی تابع جهانی[14] می باشد ؛ یک تابع قابل محاسبه که می تواند برای محاسبه هر تابع قابل محاسبه دیگری مورد استفاده قرار گیرد . تئوری UTM وجود چنین تابعی را ثابت می کند.

 

مقایسه با ماشینهای واقعی

اغلب گفته می شود که ماشینهای تورینگ برخلاف دیگر آتاماتاهای ساده تر  توان و قدرت ماشینهای واقعی را داراست , وقادر است که هر عملیاتی که یک ماشین واقعی می تواند اجرا کند را اجرا نماید.چیزی که در این جمله به آن توجه نشده آن است که تقریبا هر برنامه خاصی که بر روی یک ماشین خاص در حال اجراست در واقع هیچ چیزی نیست مگر یک  خودکارسازی محدود قطعی[15] , چراکه  ماشینی که آنرا اجرا می کند فقط می تواند بصورت محدود در پیکربندی[16] های زیادی قرار بگیرد . ماشینهای تورینگ درواقع معادلند با ماشینی که دارای مقدار فضای ذخیره سازی نا محدودی است .ممکن است بپرسیم که چرا ماشینهای تورینگ مدلهای مفیدی برای کامپیوتر های واقعی هستند .

روشهای مختلفی برای پاسخ به آن وجود دارد:

1-  هر چیزی که یک کامپیوتر واقعی قادر به محاسبه آن است , ماشین تورینگ نیز قادر به آن است , بنابراین هر جمله ای درباره محدودیتهای ماشین تورینگ  بر کامپیوتر های واقعی نیز اعمال خواهد شد.

2-  تفاوت کاذبی که وجود دارد تنها با این توانایی ماشین تورینگ که قادر است مقدار نامحدودی از داده را دستکاری کند ایجاد می شود . اگرچه براساس یک محدوده زمانی داده شده , یک ماشین تورینگ ( مانند یک ماشین واقعی ) فقط می تواند مقدار محدودی از داده را دستکاری کند.

3-  مانند یک ماشین تورینگ , یک ماشین واقعی میتواند درصورت نیاز با دریافت دیسکهای بیشتر یا رسانه های ذخیره سازی دیگر فضای ذخیره سازیش را بزرگ تر کند . اگراز فراهم کردن آن واماند, در ان صورت ممکن است که ماشین تورینگ بعنوان یک مدل غیر مفید بنظر برسد , ولی حقیقت آن است که نه ماشین تورینگ ونه ماشین واقعی هیچ کدام برای انجام محاسبات مفید به مقادیر نجومی فضای ذخیره سازی نیاز ندارند.زمان پردازش مورد نیاز معمولا خیلی بیشتر از یک مساله می باشد ؛بعنوان نمونه "busy beaver" مثالی است از ماشینهایی که تعداد خیلی زیادی از مراحل را فقط با استفاده از مقادیر ناچیزی ازتعداد بیتها بانجام می رسانند.

4-  ماشینهای واقعی خیلی پیچیده تر از یک ماشین تورینگ هستند.بعنوان مثال ماشین تورینگی که یک الگوریتم را شرح می دهد ممکن است از تعداد کم " چند صد حالت " تشکیل شده باشد , در حالی که خودکارسازی  محدود قطعی معادل روی یک ماشین واقعی دارای 1015 حالت می باشد ! این موجب می شود که نمایش DFA برای آنالیز غیر عملی باشد.                    

             

5-  ماشینهای تورینگ الگوریتمها را شرح می دهند مستقل از اینکه چقدر حافظه بکار می برند. برای هر ماشین شناخته شده حد بالای مقدار حافظه ای که دارد مشخص است ولی این محدودیت بطور قراردادی می تواند برطرف شود, ماشین های تورینگ به ما این امکان را می دهند که جملاتی در باره الگوریتم ها بسازیم که بصورت تئوریک همواره نگه داشته می شوند, بدون توجه به پیشرفتها در زمینه معماری مرسوم ماشین محاسبه گر.

 

6-  ماشین های تورینگ جملات الگوریتم را ساده سازی می کنند , الگوریتمهای اجرا شده روی ماشینهای مجرد معادل تورینگ معمولا خیلی کلی تر از همتایشان روی ماشین واقعی هستند, زیرا آنها دارای انواع داده با دقت قراردادی هستند و هرگز نباید با شرایط غیر منتظره مواجه شوند( مثلا running out of memory  )

 

از مواردی که در آن ماشینهای تورینگ مدلهای ضعیفی برای برنامه ها هستند می توان به بسیاری از برنامه های واقعی اشاره کرد , مانند سیستمهای عامل و پردازشگر کلمات , که این برنامه ها برای دریافت ورودی نامحدود در طول زمان نوشته شده اند . ماشینهای تورینگ چنین محاسبات موجودی را بخوبی مدل نمی کند ( ولی هنوزقسمتهایی از آنرا نیز مدل می کند , مانند رویه های مستقل)

محدودیت دیگر ماشینهای تورینگ این است که آنها توانایی های آرگومانهای خاص را بخوبی مدل نمی کنند . برای مثال کامپیوتر های مدرن درواقع نمونه هایی از فرم ماشینهای محاسبه گرخیلی خاص که بانام ماشینهای بادسترسی تصادفی[17]( (RAM مشخص می شوند هستند.  ابتدایی ترین تفاوت میان این ماشینها و ماشین تورینگ این است که ماشینهای تورینگ یک نوار نامحدود استفاده می کنند در حالی کهRAM ها  یک دنباله اندیس دارشمارشی[18] را استفاده می کنند(بطور نمونه یک فیلد Integer). نتیجه این تفاوت این است که براساس اندیس های حافظه ای می توان بهینه سازی های محاسباتی بکار برد که در یک ماشین تورینگ عام ممکن نیست ؛ بنابراین زمانیکه ماشینهای تورینگ  بعنوان اساس اجراهای زمانی محدود بکار می روند , یک " اشتباه محدودیت  پایین[19] "  می تواند در زمان های اجرای الگوریتم های معینی بوجود آید ( مربوط به فرض "  "false simplifyingدر ماشین تورینگ).

یک مثال از آن مرتب سازی شمارشی [20] است که از قرار معلوم در الگوریتم های مرتب سازی حد پایین   Ω(n log n)را نقض می کند . مورد دیگر جستجوی دودویی است که حد پایین خطی Ω(n) جستجو در لیست مرتب ماشینهای تورینگ را نقض می کند.



+ نوشته شده در  سه شنبه بیست و نهم خرداد 1386ساعت 11:35  توسط automata83shahed  | 

نمونه سوالات نظریه زبانها

چند تا لینک از سوالات نظریه زبان ها از جستجو در وب لاگ های دیگه همین درس (دانشگاه یزد):

http://www.ParsiBlog.com/FirendsAlbum/fa1385/a.jpg

http://www.ParsiBlog.com/FirendsAlbum/fa1385/b.jpg

http://www.ParsiBlog.com/FirendsAlbum/fa1385/c.jpg

---------------------------------------------------------------

اینم تست هاي کنکور آزاد نظريه زبان سال 1383و جواب تشريحي

http://www.divshare.com/download/45251-8fc

راستی آدرس وبلاگشون:http://fa1385.parsiblog.com

چه می کنند این بچه های دانشگاه یزد!!

-------------------------------------------------

فايل word يك سري سوالات تستي در مورد آتوماتا با جواب 
پاورپوينت هم در مورد مباحث مختلف نظريه يه توضيح داده.

http://www.divshare.com/download/31594-cd1

با تشکر از مرام بچه های دانشگاه یزد!

امیر اسمعیلی 

+ نوشته شده در  دوشنبه بیست و هشتم خرداد 1386ساعت 20:9  توسط automata83shahed  | 

نمونه سوال

نمونه سوال های نظریه زبان

 

برای دریافت روی لینک ها کلیک راست کرده و گزینه Save target az  را انتخاب کنید.

 

چند سوال با جواب

 

یک سری  نمونه سوال میان ترم به صورت فارسی و انگلیسی

 

یک سری نمونه سوال پایان ترم و جواب آن

 

یک سری دیگر امتحان میان ترم به صورت فارسی و انگلیسی

 

یک سری دیگر میان ترم در قالب فلش

 

یک سری دیگر میان ترم در قالب Jpeg

 

یک سری دیگر سوال و جواب های آنها

 

نمونه سوال

 

و ارشد 84

 

+ نوشته شده در  پنجشنبه ششم اردیبهشت 1386ساعت 2:18  توسط automata83shahed  | 

آتوماتای سلولی

آتوماتای سلولی

آتوماتای سلولی در واقع یک مدل گسسته است که در نظریه محاسبات، ریاضیات و زیست شناسی نظری مورد مطالعه قرار گرفته است. این مدل شامل یک شبکه ی منظم و متناهی از سلول هاست که هرکدام از این سلول ها در یکی از تعداد متناهی حالات تعریف شده قرار دارد. در این مدل زمان نیز گسسته است. حالت هر سلول در زمان t تابعی از حالت خود سلول و حالات تعداد متناهی از سایر سلول ها در زمان t-1 است. هر یک از این سلول ها را همسایه و مجموعه ی آنها را همسایگی می نامند.

این همسایه ها موقعیت مشخصی نسبت به سلول مرکزی دارند که تغییر هم نمی کند.

همه ی سلول ها قاعده های یکسانی برای به روزرسانی حالت خود، از روی حالت همسایگی دارند. در هر واحد زمانی قاعده ها بر روی کل شبکه اعمال می شوند و به اصطلاح یک نسل جدید پدید می آید.

 

خلاصه

یک مثال از آتوماتای سلولی میتواند یک کاغذ شطرنجی نامتناهی باشد. در این مثال هر کدام از مربع ها یک سلول درنظر گرفته می شود، سلولی که می تواند در یکی از دو حالت ممکن سفید یا سیاه باشد. همسایگی هر سلول نیز 8 مربع اطراف آن در نظر گرفته می شود. بنابراین 2^9=512 الگوی مختلف برای یک سلول و همسایگانش وجود دارد. قاعده های یک آتوماتای سلولی می تواند در قالب یک جدول ارایه شود. این جدول برای هر یک از 512 حالت مشخص می کند که سلول مرکزی در واحد بعدی زمان سفید خواهد شد یا سیاه. این در واقع یک مثال از آتوماتای سلولی دوبعدی است. بازی زندگی (Conway's Game of Life) محبوبترین آتوماتای سلولی از این نوع است.

در ابتدای کار (نسل صفر) معمولا فرض می شود کل شبکه بجز تعداد متناهی از سلول های آن در یک حالت یکسان قرار دارند. گاهی نیز فرض می شود بجز تعداد متناهی از سلول ها، باقی شبکه با یک الگوی متناوب پوشیده شده است. در آتوماتای سلولی تک بعدی معمولا فرض اخیر در نظر گرفته می شود.

آتوماتای سلولی اغلب روی یک شبکه متناهی شبیه سازی می شود تا یک شبکه نامتناهی. به عنوان مثال در آتوماتای 2 بعدی بجای یک صفحه ی نامتناهی از یک مستطیل استفاده می شود. مشکل شبکه های متناهی نحوه ی برخورد با سلول های کناری یا مرزی است. به هر حال این سلول ها، بر روی دیگر سلول های شبکه تاثیر گذارند. بنابراین نحوه ی برخورد با آنها اهمیت دارد. یک روش آن است تا اجازه دهیم این سلول های کناری همواره در حالت ثابتی باقی بمانند. روش دیگر، تغییر در تعریف همسایگی برای این سلول هاست. شاید بگویید کافیست برای این سلول ها تعداد همسایه ها را کاهش دهیم، اما توجه کنید که در این صورت مجبور به تعریف قوانین جدید نیز خواهید شد. بنابراین معمولا با این سلول ها بصورت حلقوی (Toroidal) برخورد می کنند بطوریکه چپ ترین سلول یک ردیف، همسایه راست ترین سلول همان ردیف و بالاترین سلول هر ستون، همسایه پایین ترین سلول همان ستون درنظر گرفته می شود. برای درک این شرایط، تصور کنید ابتدا لبه های چپ و راست مستطیل را به هم وصل کرده، سپس بالا و پایین لوله ی بدست آمده را به هم چسبانده اید. نتیجه یک چنبره خواهد بود.

 

 

 

برای آتوماتاهای با ابعاد دیگر نیز روش مشابهی بکار گرفته می شود. بدین ترتیب مشکل همسایگی در مرزها حل خواهد شد. در اینجا برای تشریح این مسئله یک مثال می آوریم. آتوماتایی را درنظر بگیرد که  بر روی آن تعریف شده است. واضح است که برای محاسبه ی حالت چپ ترین و راست ترین سلول های این آتوماتا دچار مشکل می شویم. در صورتیکه اگر شبکه ی این آتوماتا را بصورت یک حلقه درنظر بگیریم، این مشکل برطرف خواهد شد.

 

آتوماتای سلولی در زیست شناسی

بعضی از موجودات زنده بطور طبیعی در عملکردشان از آتوماتای سلولی بهره می برند. بنابراین رفتار آنها توسط آتوماتای سلولی قابل شبیه سازی است. به عنوان مثال الگو های رنگی روی سطح بعضی صدف های دریایی مانند Conus توسط یک آتوماتای سلولی طبیعی ساخته می شوند. در این نوع صدف یاخته های رنگی (سلول هایی با توانایی تولید رنگ) بر روی یک نوار باریک در طول لب صدف قرار دارند. هر یاخته ی رنگی خود را بر اساس یاخته های اطراف خود به یک رنگ مشخص در می آورد. به مرور که صدف رشد می کند الگوی رنگی تولید شده بر روی سطح صدف بالا می رود.

 

 

 

مثال دیگر گیاهان هستند که مکانیسم تنفسی آنها بر اساس یک آتوماتای سلولی است. در اینجا روزنه های روی هر برگ همچون سلول های آتوماتا عمل می کنند.

 

نرم افزار

نرم افزارهای زیادی برای شبیه سازی رفتار آتوماتای سلولی نوشته شده به عنوان مثال این یکی را امتحان کنید.

منبع : Wikipedia

آخرین بروز رسانی : 10/2/86

 

+ نوشته شده در  سه شنبه چهارم اردیبهشت 1386ساعت 23:32  توسط حامد احمدی  | 

بمب گوگلی برای خلیج فارس

سایت های جستجوگر مثل گوگل صفحات وب را با معیارهای مختلف و متنوعی امتیازدهی می کنند
اگر یه واژه رو جستجو کنید نتایج جستجو بر اساس امتیاز صفحات برای شما لیست می شن

حالا یکی از این معیارها تعداد لینک هایی که از سایت های دیگر به یک صفحه داده شده
بمب گوگلی این که یک گروه بزرگی با هم متحد بشن و به یک صفحه ی خاص لینک بدن

یکی از این بمب ها، بمب خلیج فارس که ایرانی ها کاشتنش

By: X2 ‌

+ نوشته شده در  جمعه سی و یکم فروردین 1386ساعت 18:55  توسط automata83shahed  | 

مطالب قدیمی‌تر