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

אין שינוי בגודל ,  לפני 3 שנים
מ
בוט החלפות: לעתים, דוגמה\1, בהינתן
תגית: עריכת קוד מקור 2017
מ (בוט החלפות: לעתים, דוגמה\1, בהינתן)
'''שפה רקורסיבית''', או '''שפה כריעה''' היא מונח ב[[מתמטיקה]], [[לוגיקה]] ו[[מדעי המחשב]], המתאר [[שפה פורמלית]] ([[קבוצה (מתמטיקה)|קבוצה]] של רצפים סופיים של סמלים שנלקחו  מאלף-בית מסוים) המהווה [[קבוצה רקורסיבית|תת קבוצה רקורסיבית]] של הקבוצה של כל הרצפים הסופיים מעל ה[[אלפבית]] של השפה. באופן שקול, שפה רשמית היא רקורסיבית אם קיימת מכונת טיורינג טוטאלית ([[מכונת טיורינג]] העוצרת על כל קלט), אשר בהנתןבהינתן רצף סופי של סימנים כקלט, מקבלת אם הרצף שייך לשפה ודוחה אחרת. שפות רקורסיבית שפות נקראות גם '''[[כריעות|כְּרִיעׂות]]'''.
 
רעיון הכריעוּת ניתן להרחבה על ידי [[מודל חישובי|מודלים חישוביים אחרים]]. למשל, אפשר לדבר על שפות כריעות ב[[מכונת טיורינג לא-דטרמיניסטית]]. לכן, בכל פעם שיש אי-בהירות, "שפה רקורסיבית" בעלת משמעות זהה לשפה הניתנת להכרעה על ידי מכונת טיורינג.
 
המחלקה של כל השפות הרקורסיבית שפות נקראת בספרות '''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>