اهداف رفتاری:
دانشجو پس از مطالعه این فصل با مفاهیم زیر آشنا خواهد شد:
مفاهیم نمادگذاری و مفهوم تابع
نظریه مجموعه ها
مفهوم استقراء ریاضی
گراف و انواع آن
┌4.5┐= 5
نماد ┌x┐ را جزء صحیح بالای x می نامیم.
└4.5┘= 4
نماد └x┘ را جزء صحیح پایین x می نامیم.
پایه استقراء: عبارت به ازاء n=1(یا هر مقدار اولیه دیگر) درست است.
فرض استقراء: عبارت برای هر عدد دلخواه n≥1(یا هر مقدار اولیه دیگر) درست است.
گام استقراء: اگر عبارت به ازاء n درست است، آنگاه به ازاء n+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
فرض کنید که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 خواهد بود.
فایل پاورپوینت 225 اسلاید
دانلود پاورپوینت نظریه زبانها و ماشین ها