הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

5.1. הגדרה

תהיינה plot:\[{L_1},{L_2} \in {\Sigma ^*}\] שפות. פונקציה plot:\[f:{\Sigma ^*} \to {\Sigma ^*}\] נקראת רדוקציה מ-plot:\[{L_1}\] ל-plot:\[{L_2}\] אם היא מקיימת:

  1. plot:\[f\] מלאה (מוגדרת על כל קלט plot:\[x \in {\Sigma ^*}\]). (נשים לב ש-plot:\[f\] אינה מוגדרת רק עבור המילים השייכות ל-plot:\[{L_1}\]!).
  2. plot:\[f\] ניתנת לחישוב (קיימת מ"ט שמחשבת אותה).
  3. תקפות: plot:\[\forall x,x \in {L_1} \Leftrightarrow f\left( x \right) \in {L_2}\]

אם קיימת plot:\[f\] כנ"ל נאמר כי plot:\[{L_1}\] ניתנת לרדוקציה ל-plot:\[{L_2}\], ונסמן: plot:\[{L_1} \leqslant {L_2}\].

נבהיר בציור את מושג התקפות, על מנת לעשות אותו אינטואיטיבי יותר. יהיו plot:${L_1},{L_2}$ שפות, ו-plot:\[\overline {{L_1}} ,\overline {{L_2}} \] השפות המשלימות להן (plot:$L \cup \overline L  = {\Sigma ^*}$).  אזי:

הרדוקציה plot:$f$ מעבירה איברים שהיו בשפה plot:${L_1}$ אל איברים ב-plot:${L_2}$ ומעבירה איברים מ-plot:$\overline {{L_1}} $ אל plot:$\overline {{L_2}} $.

דוגמאות:

  • plot:\[{L_D} \leqslant {L_u}\]: נראה פונקציה plot:\[f\] המקיימת את הגדרת הרדוקציה: plot:\[f\left( {\left\langle M \right\rangle } \right) \triangleq \left( {\left\langle M \right\rangle ,\left\langle M \right\rangle } \right)\].
  • plot:\[{L_u} \leqslant HP\]. ניקח את הפונקציה plot:\[f\left( {\left\langle M \right\rangle ,\left\langle x \right\rangle } \right) \triangleq \left( {\left\langle {M'} \right\rangle ,\left\langle x \right\rangle } \right)\], כאשר plot:\[M'\] היא מ"ט המוגדרת באופן הבא: plot:\[M'\] זהה ל-plot:\[M\] למעט אם plot:\[M\] נכנסת ל-plot:\[{q_R}\], ואז plot:\[M'\] נכנסת ללולאה אינסופית, כלומר אם plot:\[\delta \left( {q,a} \right) = \left( {{q_R},...} \right)\] אזי plot:\[\delta '\left( {q,a} \right) = \left( {q,a,S} \right)\].


תגיות המסמך:

לפרק הקודם5. רדוקציות
לפרק הבא5.2. משפט הרדוקציה
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד