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