ماشین های مختلف

ماشین مور                          http://en.wikipedia.org/wiki/Moore_machine

ماشین ملی                         http://en.wikipedia.org/wiki/Mealy_machine

ماشن مجازی        http://en.wikipedia.org/wiki/Virtual_finite_state_machine

زمان امتحان پایان ترم

امتحان پایان ترم نظریه زبانها بدون تغییر در تاریخ ۶ تیر ساعت ۸:۳۰ الی ۱۰:۳۰ بصورت تشریحی و کتاب بسته برگزار می شود.

امتحان شماره ۱

امتحان شماره ۱ نظریه زبانها در تاریخ ۲۱/۱۲/۸۴ به صورت تستی و کتاب باز حاوی ۲۰ سوال برگزار شد که سوالات این آزمون به همراه پاسخ تستی به صورت فایل pdf و doc قابل دسترسی می باشد:

دانلود فایل pdf  

دانلود فایل doc

دانلود فایل rar

مهدی نوروزی

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

در ریاضیات، منطق و علوم کامپوتر، زبان بازگشتی برشمردنی یک نوع زبان صوری است که تا حدی تصمیم پذیر یا تصمیم پذیر تورینگ نیز نامیده می شود.این نوع زبان در سلسله مراتب زبان های صوری چامسکی با عنوان زبان نوع صفر شناخته می گردد.کلاس زبان های بازگشتی برشمردنی 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

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

 

                                               http://en.wikipedia.org/wiki/Recursively_enumerable_language

 

موادامتحانی‌ وضرایب‌ رشته‌ های‌‌ دوره‌ کارشناسی‌ ارشد کامپیوتر

 

علوم کامپیوتر

1.زبان‌ عمومی و تخصصی‌,2.دروس پایه (ریاضی1, 2,آمارو احتمال, مبانی کامپیوتر), 3. ریاضیات گسسته,4.ساختمان داده هاو الگوریتمها, 5. اصول سیستمهای کا مپیوتری, 6. نظریه اتوماتاو زبانها, 7. آنالیزعددی.
ضرایب به ترتیب دروس:
(2, 6, 3, 3, 3, 3, 3) ‌

********

مجموعه مهندسی فناوری اطلاعات it
1. تجارت الکترونیکی 2. سیستمهای چند‌رسانه‌ای
3.مدیریت سیستمهای اطلاعاتی
4.امنیت اطلاعات5.شبکه‌های کامپیوتری
6.مهندسی فناوری اطلاعات( it )

1. زبان تخصصی, 2.دروس مشترک (ساختمانهای گسسته,ساختمانهای داده ها,طراحی الگوریتم, مهندسی نرم‌افزار, شبکه‌ها ی کامپیوتری) ,3.اصول و مبا نی مدیریت,4.اصول طرا حی پایگاه‌ داده‌ها,5.هوش مصنوعی,6 .سیستمها ی عامل,7.معماری کامپیوتر.
ضرایب به ترتیب دروس:
1.تجارت الکترونیکی(1, 2, 1, 1, 1, 1, 0)
2.سیستمهای چندرسانه‌ای(1, 2, 1, 1, 1, 1, 0)
ه3.مدیریت سیستمهای ا طلاعاتی(1, 2, 2, 1, 1, 1, 0)
4.امنیت اطلاعات(1,‌ 2, 0, 1, 1, 1, 1)
5.شبکه‌های کامپیوتری(1, 2, 0, 1, 1, 1, 1)
6.ضرایب همانندگرایش تجارت الکترونیکی

********

مجموعه‌ مهندسی‌کامپیوتر
1. معماری‌ کامپیوتر
2. هوش‌ مصنوعی
‌3. نرم‌افزار

1.زبان عمومی وتخصصی(انگلیسی‌) , 2.ریاضیات(ریاضیات‌ مهندسی,آمارواحتمالات,محاسبات‌عددی‌ , ساختمانهای‌گسسته ‌), 3. دروس مشترک (ساختمان‌ داده ها,نظریه ز بان‌هاوماشین‌ها,مدارهای‌منطقی‌,معماری‌کامپیوتر,سیستم‌ عامل), 4 .دروس تخصصی معماری ‌ کامپیوتر (مدارهای الکتریکی, vlsi ,الکترونیک‌دیجیتال‌,انتقال‌ داده‌) , 5 .دروس ‌ تخصصی‌ هوش ‌ مصنوعی (مدارهای‌الکتریکی‌,طراحی‌ الگوریتم‌ها,هوش مصنوعی‌), 6.درو س تخصصی نرم‌افزار(کامپایلر,زبانهای‌ برنامه‌سازی‌,طراحی الگوریتم‌, پایگاه‌ داده‌).
ضرایب به ترتیب دروس:
1.معماری‌کامپیوتر(1, 2, 4, 2, 0, 0)
2. هوش‌ مصنوعی(1, 2, 4, 0, 2, 0)
3.نرم‌افزار(1, 2, 4, 0, 0, 2 )

 توجه: این اطلاعات مربوط به آزمون کارشناسی ارشد سال ۸۴ می باشد.