טבלת המעבר היא בעצם ייצוג טבלאי של פונקציית המעבר. זה לוקח שני ארגומנטים (מצב וסמל) ומחזיר מצב ('המצב הבא').
טבלת מעבר מיוצגת על ידי הדברים הבאים:
- עמודות מתאימות לסמלי קלט.
- שורות מתאימות למדינות.
- ערכים תואמים למצב הבא.
- מצב ההתחלה מסומן על ידי חץ ללא מקור.
- מצב הקבלה מסומן בכוכב.
דוגמה 1:
פִּתָרוֹן:
טבלת מעבר של DFA נתון היא כדלקמן:
| מצב נוכחי | המצב הבא עבור קלט 0 | מצב הקלט הבא 1 |
|---|---|---|
| →q0 | ש1 | ש2 |
| ש1 | q0 | ש2 |
| *q2 | ש2 | ש2 |
הֶסבֵּר:
- בטבלה לעיל, העמודה הראשונה מציינת את כל המצבים הנוכחיים. מתחת לעמודות 0 ו-1, המצבים הבאים מוצגים.
- ניתן לקרוא את השורה הראשונה של טבלת המעבר ככאשר המצב הנוכחי הוא q0, בקלט 0 המצב הבא יהיה q1 ובקלט 1 המצב הבא יהיה q2.
- בשורה השנייה, כאשר המצב הנוכחי הוא q1, בכניסה 0, המצב הבא יהיה q0, ובקלט 1 המצב הבא יהיה q2.
- בשורה השלישית, כאשר המצב הנוכחי הוא q2 בכניסה 0, המצב הבא יהיה q2, ובקלט 1 המצב הבא יהיה q2.
- החץ המסומן ל-q0 מציין שזהו מצב התחלה ועיגול המסומן ל-q2 מציין שזהו מצב סופי.
דוגמה 2:
פִּתָרוֹן:
טבלת המעבר של NFA נתונה היא כדלקמן:
| מצב נוכחי | המצב הבא עבור קלט 0 | מצב הקלט הבא 1 |
|---|---|---|
| →q0 | q0 | ש1 |
| ש1 | ש1, ש2 | ש2 |
| ש2 | ש1 | ש3 |
| *q3 | ש2 | ש2 |
הֶסבֵּר:
- ניתן לקרוא את השורה הראשונה של טבלת המעבר ככאשר המצב הנוכחי הוא q0, בקלט 0 המצב הבא יהיה q0 ובקלט 1 המצב הבא יהיה q1.
- בשורה השנייה, כאשר המצב הנוכחי הוא q1, בקלט 0 המצב הבא יהיה q1 או q2, ובקלט 1 המצב הבא יהיה q2.
- בשורה השלישית, כאשר המצב הנוכחי הוא q2 בכניסה 0, המצב הבא יהיה q1, ובקלט 1 המצב הבא יהיה q3.
- בשורה הרביעית, כאשר המצב הנוכחי הוא q3 בכניסה 0, המצב הבא יהיה q2, ובקלט 1 המצב הבא יהיה q2.