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

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

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

4.1. דוגמאות לשפות במחלקות

שפות השייכות ל-R: plot:[Sigma^{*}], plot:[phi], שפות רגולריות.

שפות השייכות ל-RE:

  • כל שפה שב-R.
  • שפה של כל אוטומט.
  • שפת העצירה HP, המוגדרת כך: plot:[HP = left{ {leftlangle M ight angle ,leftlangle x ight angle |{ ext{ }}M{ ext{ stops on input }}x} ight}]
  • השפה האוניברסלית: plot:[{L_u} = left{ {leftlangle M ight angle ,leftlangle x ight angle |M{ ext{ accepts on the input }}x} ight}]
  • שפת האלכסון: plot:[{L_D} = left{ {leftlangle M ight angle |leftlangle M ight angle  in Lleft( M ight)} ight}]. שפה זו היא שפת כל המכונות המקבלות את הייצוג של עצמן.

תרגיל: לאיזו מחלקה שייכת השפה הבאה: plot:${L_1} = left{ {leftlangle M ight angle |Lleft( M ight) in RE} ight}$?

תשובה: מכיוון שלכל plot:$M$ כלשהי ל-plot:$Lleft( M ight)$ קיימת מכונה המקבלת כל מילה בשפה, אזי מתקיים כי לכל plot:$M$, plot:$Lleft( M ight) in RE$. כלומר plot:${L_1}$ הינה אוסף ייצוגי כל מכונות טיורינג. עבור כל מחרוזת, ניתן להכריע האם היא מייצג מכונת טיורינג. לפיכך plot:${L_1} in R$.

תגיות המסמך:

לפרק הקודם4. בעיות הכרעה
לפרק הבא4.2. המחלקה של שפת העצירה
מאת: דנה

החלק הראשון

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

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

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

מאת: חשוון

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