תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף

}}

 

להלן דוגמאות לשפות כריעות:

# השפה <math>\Sigma^*</math> – לכל קלט, בצעד החישוב הראשון המכונה עוברת ל־<math>q_{acc}</math>.

# כל שפה רגולרית – אוטומט סופי הוא מקרה פרטי של מכונת טיורינג, לכן מ"ט מסוגלת לחשב כל מה שאוטומט סופי יכול.

# <math>\}</math> מספר האפסים בקלט שווה למספר האחדים <math>L=\{ x\in\{0,1\}^* \mid</math>. (זו שפה לא-רגולרית)

 

נוכל כמובן להגדיר את מחלקת השפות הכריעות.