תורת החישוב ושפות פורמליות
דומיין זה בודק שפות פורמליות ומודלים חישוביים: ביטויים רגולריים, אוטומטים סופיים, דקדוקים חסרי הקשר, מכונות טיורינג ושאלות הכרעה. השאלות דורשות מעבר בין ייצוגים וזיהוי גבולות הכוח החישובי.
כללים
- אלפבית הוא קבוצת תווים; מחרוזת היא רצף סופי; שפה היא קבוצת מחרוזות.
- שפה רגולרית ניתנת לתיאור על ידי ביטוי רגולרי, DFA או NFA; NFA ו-DFA שקולים בכוחם.
- רגולריות נסגרת תחת איחוד, שרשור, כוכב קליני, משלים וחיתוך.
- דקדוק חסר הקשר מתאר שפות עם מבנה מקונן, כמו סוגריים מאוזנים; אוטומט מתאים הוא PDA.
- מכונת טיורינג היא המודל הכללי; בעיית העצירה אינה ניתנת להכרעה.
- למת הניפוח היא תנאי הכרחי לאי-רגולריות, לא הוכחה מספקת לרגולריות.
דוגמה מעובדת
DFA מעל {0,1} שמקבל מחרוזות המסתיימות ב-01: מצב q0 התחלתי, q1 אחרי 0, q2 אחרי 01. מ-q0 על 0 עוברים ל-q1, על 1 נשארים q0. מ-q1 על 1 עוברים ל-q2, על 0 נשארים q1. מ-q2 על 0 עוברים ל-q1, על 1 נשארים q0. מצב מקבל הוא q2. הקלט 101: q0→q1→q2→q2, מתקבל. הקלט 110: q0→q0→q1→q0, נדחה.
מלכודות
- לבלבל בין NFA ל-DFA ולחשוב שיש להם כוח שונה.
- לנסות ביטוי רגולרי לסוגריים מאוזנים, שאינם רגולריים.
- להשתמש בלמת הניפוח בכיוון הלא נכון.
- לשכוח מצב מקבל או מעבר חסר בתרשים.
- להניח שכל בעיה ניתנת להכרעה במכונת טיורינג.