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

תוכן שנמחק תוכן שנוסף
יעל י (שיחה | תרומות)
מ שוחזר מעריכה של 84.228.98.67 (שיחה) לעריכה האחרונה של Gran
אין תקציר עריכה
שורה 26:
#כל שפה סופית <math>L=\{ a_1, a_2, \ldots, a_n \}</math> – נבדוק כל מילה אפשרית. מכיוון שכמות המילים סופית, נדרשים מספר סופי של מצבים (ובפרט, זו [[אוטומטים ושפות פורמליות/תכונות של שפות רגולריות|שפה רגולרית]])
# כל שפה רגולרית – אוטומט סופי הוא מקרה פרטי של מכונת טיורינג, לכן מ"ט מסוגלת לחשב כל מה שאוטומט סופי יכול.
# <math>\}</math> מספר האפסים בקלט שווה למספר האחדיםהאחדות <math>L=\{ x\in\{0,1\}^* \mid</math>. (זו שפה לא-רגולרית)