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

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

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

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