הצגת המקור של הדף "שפה רקורסיבית"

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

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

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

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

== דוגמאות ==
שפות תלויות-הקשר גם הן רקורסיביות. לדוגמה השפה <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>

== סגירוּת אלגברית ==
רקורסיבית שפות [[סגירות (אלגברה)|סגורה]] תחת הפעולות הבאות. כלומר, אם ''L'' ו-''P'' הן שתי שפות רקורסיביות, השפות הבאות גם הן רקורסיביות:
* כוכב קלין <math>L^*</math>
* התמונה (φ(L תחת [[הומומורפיזם]]  φ (כלומר e-free homomorphism)
* השרשור <math>L \circ P</math>
* האיחוד <math>L \cup P</math>
* החיתוך <math>L \cap P</math>
* המשלים של <math>L</math>
* קבוצת ההפרש <math>L - P</math>

[[קטגוריה:רקורסיה]]
[[קטגוריה:שפות פורמליות]]
[[קטגוריה:חישוביות]]