بخشی از پاورپوینت
اسلاید 1 :
نظريه زبانها و ماشين ها
فصل اول: مقدمه اي بر تئوري محاسبات
اسلاید 2 :
فهرست مطالب
مقدمات رياضي و علامت گذاري
مجموعه ها
توابع و روابط
گراف ها و درخت ها
روشهاي اثبات
مفاهيم اساسي نظريه زبانها
تعريف زبان
گرامر
ماشين
اسلاید 3 :
مقدمات رياضي و علامت گذاري مجموعه ها
اسلاید 4 :
مجموعه ها
اسلاید 6 :
زير مجموعه ها، تابع، رابطه
اسلاید 7 :
رابطه هم ارزي
اسلاید 8 :
افراز مجموعه ها
در نظر بگيريد مجموعه مرجع U را داشته باشيم و زير مجموعه هايي از اين مجموعه که با هم اشتراک نداشته باشند و در عين حال اجتماع تمامي اين مجموعه هاي کوچکتر، ميتواند مجموعه U را تشکيل دهد. در اين صورت به اين مجموعه هاي کوچکتر يک افراز از مجموعه U ميگويند.
در شکلهاي مقابل دو افراز از مجموعه U را مشاهده ميکنيد.
روابط هم ارزي اين قابليت را دارند که مجموعه دامنه را افراز نمايند.
براي مثال همنهشتي با پيمانه 3 مجموعه اعداد صحيح غير منفي را به سه زير مجموعه افراز ميکند:
عناصري هم ارز 0 هستند؛
عناصري که هم ارز 1 هستند؛
عناصري که هم ارز 2 هستند.
اسلاید 9 :
گراف ها و درخت ها
يک گراف را بصورت زوج مرتبي شامل مجموعه راس ها و مجموعه اي از يالها به شکل G(V,E) نشان ميدهيم.
V مجموعه راس ها و E مجموعه يالها ميباشد
گراف ها ميتوانند جهت دار باشند و يا بدون جهت. در گرافهاي جهت دار، وجود ارتباط بين دو راس و تعيين راس مبدا اهميت دارد.
گراف ها ميتوانند وزن دار باشند، در گرافهاي وزن دار، هر يال داراي وزن ميباشد.
اسلاید 10 :
درخت ها
اسلاید 11 :
روش هاي اثبات (اثبات مستقيم، استقرا و برهان خلف)
اسلاید 15 :
بخش دوم- مفاهيم زبان، گرامر و ماشين
بدون تمرکز بر سخت افزارها و ويژگي هاي ماشين ها، مفاهيم زبان را بصورت صوري معرفي ميکنيم.
تمامي تجهيزات کامپيوتري و زبانهاي برنامه نويسي داراي زبان ارتباطي خاص خود هستند که از قوانين معرفي شده در اين فصل تبعيت ميکنند
اسلاید 16 :
بخش دوم- مفاهيم زبان، گرامر و ماشين
اسلاید 18 :
زبان
اسلاید 19 :
عمليات روي زبانها
اسلاید 20 :
گرامرها
براي مطالعه زبانها، از نظر رياضي ما نيازمند مكانيزمي براي توصيف آنها هستيم.
استفاده از زبان محاوره اي برای توصیف یک زبان، غير دقيق و مبهم است.
نمادهاي مجموعه كه قبلاً معرفي شدند مناسب است ولي ناكافي هستند.
در اينجا يك مكانيزم رايج و قوي به نام گرامر را معرفي ميكنيم.
يك گرامر براي يك زبان به ما ميگويد كه آيا يك جمله خوش ساخت است يا خير.
قوانين گرامري براي زبان محاوره اي هم وجود دارند:
يكي از روشهاي ساخت جمله فاعل + فعل است: علي رفت.
در گرامر بالا جمله رفت علي صدق نميكند.
البته اين گرامر بسيار ساده است و زبان محاوره اي قوانين زيادي را شامل ميشود.
