שפה רקורסיבית

סוג של שפה פורמלית

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

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

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

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

דוגמאות

עריכה

שפות תלויות-הקשר גם הן רקורסיביות. לדוגמה השפה   או בכתיב הפורמלי:

 

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

עריכה

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

  • כוכב קלין  
  • התמונה (φ(L תחת הומומורפיזם  φ (כלומר e-free homomorphism)
  • השרשור  
  • האיחוד  
  • החיתוך  
  • המשלים של  
  • קבוצת ההפרש