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

بخشی از پاورپوینت

اسلاید 1 :

پاورپوینت و خلاصه کتاب 

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

اسلاید 2 :

فصل اول: ریاضیات مقدماتی
اهداف رفتاري:
دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد:

مفاهیم نمادگذاری و مفهوم تابع
نظریه مجموعه ها
مفهوم استقراء ریاضی
گراف و انواع آن

اسلاید 3 :

1-1 نمادگذاری
نماد ┌x┐: اشاره به کوچکترین عدد صحیح بزرگتر یا مساوی عدد حقیقی x دارد. ┌-3.7┐=-3
┌4.5┐= 5
نماد ┌x┐ را جزء صحیح بالای x می نامیم.

نماد └x┘: اشاره به بزرگترین عدد صحیح کوچکتر یا مساوی عدد حقیقی x دارد. └-3.7┘=-4
└4.5┘= 4
نماد └x┘ را جزء صحیح پایین x می نامیم.

اسلاید 4 :

1-2 توابع
تابع f: تشکیل شده از یک متغیر با قاعده و قانون می باشد که به ازاء یک مقدار x ، مقدار منحصر به فردی را به f(x) نسبت می دهد.
نمودار یک تابع: مجموعه ای است از کلیه زوجهای مرتب که بوسیله تابع تعیین می شوند.
دامنه یک تابع: مجموعه مقادیری است که تابع به ازاء آنها تعریف می شود

اسلاید 5 :

1-2 توابع
تابع جامع: تابعی که از XبهY یک رابطه دودویی روی X*Y را داراست.
تابع جزئی: رابطه بین X*Yاست وقتی که
єf [x,y2]و єf [x,y1]
تابع یک به یک: تابعی که در آن هر عنصر xبه یک عنصر مجزا در برد تصویر شود.

اسلاید 6 :

1-3 نظریه مجموعه ها
نمادهای مجموعه :
نماد є به معنای عضویت است. بطوریکه x є X مشخص می کند که x یک عضو یا عنصر مجموعه Xاست.
از دو براکت{ } برای تعریف یک مجموعه استفاده می شود.
X= { 1,2,3 }
مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند.
{n l n=m² for some natural number m}

اسلاید 7 :

1-3 نظریه مجموعه ها
یک مجموعه با اعضایش مشخص می شود.
اگرY یک زیر مجموعه از Xباشد و X≠Yآنگاه به Yیک زیر مجموعه کامل X میگوئیم.

اسلاید 8 :

1-3 نظریه مجموعه ها
اجتماع دو مجموعه به صورت زیر تعریف می شود:
XυY = { z l z є X or z є Y}
اختلاف دو مجموعه به صورت زیر تعریف می شود:
X-Y = { z l z є X and z є Y}
مکمل X نسبت به U مجموعه عناصری در U است که در X نمی باشد.

اسلاید 9 :

1-4 استقراء ریاضی
مفاهیم مورد استفاده در استقراء ریاضی
پایه استقراء: عبارت به ازاء n=1(یا هر مقدار اولیه دیگر) درست است.
فرض استقراء: عبارت برای هر عدد دلخواه n≥1(یا هر مقدار اولیه دیگر) درست است.
گام استقراء: اگر عبارت به ازاء n درست است، آنگاه به ازاء n+1 نیز درست می باشد.

اسلاید 10 :

1-4 استقراء ریاضی
مثال:
برای کلیه اعداد صحیح مثبت نشان می دهیم که
پایه استقراء: برای n=1داریم:
فرض استقراء:فرض کنید که برای یک عدد صحیح مثبت دلخواه n داریم:
گام استقراء:لازم است که نشان دهیم:

اسلاید 11 :

1-5 قضایا و پیش قضایا
قضیه در لغت به معنای گفتاری است که صحت آن باید اثبات شود.
مثال:برای هر عدد صحیح 0n› داریم:
پیش قضیه به عنوان یک قضیه کمکی برای اثبات قضایای دیگر به کار می رود.

اسلاید 12 :

1-6 گراف ها
اجزای یک گراف:
دایره ها نشانگر گره ها(vertices)
خطوط ارتباط گره ها نشانگر لبه (edge)

اسلاید 13 :

1-6 گراف ها
گراف جهت دار: اگر هر لبه گراف دارای جهت باشد به آن گراف جهت دار(digraph)می گویند.
مسیر(path): در یک گراف جهت داربه دنباله ای از گره ها که بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود.
گراف وزن دار: اگر به لبه ها مقادیری تخصیص یافته باشدبه آن مقادیر وزن و به آن گراف،گراف وزن دار می گوییم.

اسلاید 14 :

1-6 گراف ها
چرخه(cycle): به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود.
گراف چرخه ای: اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود.
مسیر ساده: مسیری که از از یک گره دو بار عبور نکند.
طول(length)یک مسیر در یک گراف وزن دار برابر مجموع وزنهای مسیر است.

اسلاید 15 :

1-6 گراف ها
گراف بدون جهت: گرافی که لبه های ان هیچ جهتی نداشته باشند.
گراف متصل:گرافی بدون جهت که بین هر دو گره دلخواه از آن یک مسیر مشخص وجود داشته باشد.
درخت: یک گراف بدون جهت، پیوسته و بدون چرخه است.
درخت ریشه دار:درختی که در آن یک گره به عنوان ریشه درخت انتخاب می شود.
درخت پوشا برای G: یک زیر گراف متصل است که اولاً شامل همه گره های G بوده و ثانیاً یک درخت باشد.

اسلاید 16 :

فصل دوم: زبان ها
اهداف رفتاري:
دانشجو پس از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد:

مفاهیم رشته و زبان
مشخصات زبان ها
مجموعه های با قاعده

اسلاید 17 :

زبان: یک زبان یک مجموعه از رشته ها روی یک الفبا است.
رشته: یک رشته روی یک مجموعه X یک دنباله متناهی از عناصر Y است.
الفبای زبان: به مجموعه عناصری که رشته ها از آن ساخته می شوند الفبای زبان گوئیم.
رشته تهی: رشته فاقد عنصر را رشته تهی می نامیم که باλ نشان می دهیم.
2-1 رشته ها و زبانها

اسلاید 18 :

2-1 رشته ها و زبانها
*∑ :
فرض کنید که {a,b,c} = ∑باشد.عنصر *∑ شامل:
λ : طول 0
a b c : طول 1
aa ab ac ba bb bc ca cb cc : طول 2
aaa aab aac aba abb abc aca acb acc : طول3
baa bab bac bba bbb bbc bca bcb bcc
caa cab cac cba cbb cbc cca ccb ccc

اسلاید 19 :

2-1 رشته ها و زبانها
تعریف زبان
یک زبان روی یک الفبای ∑ یک زیر مجموعه از *∑ است.
الحاق: الحاق یک عمل دودویی است که دو رشته را به عنوان ورودی گرفته و با چسباندن آنها در کنار هم یک رشته جدید ایجاد می کند. الحاق عمل اصلی در تولید رشته هاست.
یک زبان شامل رشته هایی روی الفبا است.

اسلاید 20 :

2-1 رشته ها و زبانها
فرض کنید کهvє∑* باشد.الحاق uوv، که به صورت uv نوشته می شودف یک عمل دودویی روی ∑* است که به صورت زیر تعریف می شود:
(iپایه: اگر length(v)=0 باشد. آنگاهגּv= و uv=u خواهد بود.
(ii گام بازگشت: فرض کنید که v یک رشته با طول length(v)=n›0 باشد. در اینصورت ، به ازای برخی رشته هایw با طول n-1و a є ∑، v=waو در نتیجه uv=(uw)a خواهد بود.