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

اهداف رفتاری:

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

 مفاهیم نمادگذاری و مفهوم تابع

 نظریه مجموعه ها

 مفهوم استقراء ریاضی

 گراف و انواع آن

┌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 اسلاید