שפה רקורסיבית – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־04:29, 2 בדצמבר 2017

שפה רקורסיבית, או שפה כריעה היא מונח במתמטיקה, לוגיקה ומדעי המחשב, המתאר שפה פורמלית (קבוצה של רצפים סופיים של סמלים שנלקחו מאלף-בית מסוים) המהווה תת קבוצה רקורסיבית של הקבוצה של כל הרצפים הסופיים מעל האלפבית של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית (מכונת טיורינג העוצרת על כל קלט), אשר בהינתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראות גם כְּרִיעׂות.

רעיון הכריעוּת ניתן להרחבה על ידי מודלים חישוביים אחרים. למשל, אפשר לדבר על שפות כריעות במכונת טיורינג לא-דטרמיניסטית. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.

המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות R, אם כי שם זה משמש לעתים גם עבור המחלקה RP.

סוג זה של שפה לא הוגדר בהיררכיה של חומסקי (Chomsky 1959). כל השפות הרקורסיבית גם ניתנות למנייה רקורסיבית (Recursively Enumerable). כל שפה רגולרית, שפה חפשית הקשר, ושפה תלוית הקשר היא גם רקורסיבית.

דוגמאות

שפות תלויות-הקשר גם הן רקורסיביות. לדוגמה השפה $L={abc,aabbcc,aaabbbccc,...}$ או בכתיב הפורמלי:

L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}

סגירוּת אלגברית

רקורסיבית שפות סגורה תחת הפעולות הבאות. כלומר, אם L ו P הן שתי שפות רקורסיביות, השפות הבאות גם הן רקורסיביות:

כוכב קלין $L^{*}$
התמונה (φ(L תחת הומומורפיזם φ (כלומר e-free homomorphism)
השרשור $L\circ P$
האיחוד $L\cup P$
החיתוך $L\cap P$
המשלים של $L$
קבוצת ההפרש $L-P$

@@ שורה 1: / שורה 1: @@
-'''שפה רקורסיבית''', או '''שפה כריעה''' היא מונח ב[[מתמטיקה]], [[לוגיקה]] ו[[מדעי המחשב]], המתאר [[שפה פורמלית]] ([[קבוצה (מתמטיקה)|קבוצה]] של רצפים סופיים של סמלים שנלקחו  מאלף-בית מסוים) המהווה [[קבוצה רקורסיבית|תת קבוצה רקורסיבית]] של הקבוצה של כל הרצפים הסופיים מעל ה[[אלפבית]] של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית ([[מכונת טיורינג]] העוצרת על כל קלט), אשר בהנתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראות גם '''[[כריעות|כְּרִיעׂות]]'''.
+'''שפה רקורסיבית''', או '''שפה כריעה''' היא מונח ב[[מתמטיקה]], [[לוגיקה]] ו[[מדעי המחשב]], המתאר [[שפה פורמלית]] ([[קבוצה (מתמטיקה)|קבוצה]] של רצפים סופיים של סמלים שנלקחו  מאלף-בית מסוים) המהווה [[קבוצה רקורסיבית|תת קבוצה רקורסיבית]] של הקבוצה של כל הרצפים הסופיים מעל ה[[אלפבית]] של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית ([[מכונת טיורינג]] העוצרת על כל קלט), אשר בהינתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראות גם '''[[כריעות|כְּרִיעׂות]]'''.
 רעיון הכריעוּת ניתן להרחבה על ידי [[מודל חישובי|מודלים חישוביים אחרים]]. למשל, אפשר לדבר על שפות כריעות ב[[מכונת טיורינג לא-דטרמיניסטית]]. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.
-המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות '''R''', אם כי שם זה משמש לעיתים גם עבור המחלקה [[RP]].
+המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות '''R''', אם כי שם זה משמש לעתים גם עבור המחלקה [[RP]].
 סוג זה של שפה לא הוגדר ב[[ההיררכיה של חומסקי|היררכיה של חומסקי]] {{Harv|Chomsky|1959}}. כל השפות הרקורסיבית גם ניתנות למנייה רקורסיבית (Recursively Enumerable). כל [[שפה רגולרית]], [[שפה חופשית הקשר|שפה חפשית הקשר,]] ו[[שפה תלוית הקשר]] היא גם '''רקורסיבית'''.
 == דוגמאות ==
-שפות תלויות-הקשר גם הן רקורסיביות. לדוגמא השפה <math>L={abc, aabbcc, aaabbbccc, ...}</math> או בכתיב הפורמלי:
+שפות תלויות-הקשר גם הן רקורסיביות. לדוגמה השפה <math>L={abc, aabbcc, aaabbbccc, ...}</math> או בכתיב הפורמלי:
 : <math>L=\{\,w \in \{a,b,c\}^* \mid w=a^nb^nc^n \mbox{ for some } n\ge 1 \,\}</math>