جدول الانتقال هو في الأساس تمثيل جدولي لوظيفة الانتقال. يأخذ وسيطتين (حالة ورمز) ويعيد الحالة ('الحالة التالية').
يتم تمثيل الجدول الانتقالي بالأشياء التالية:
- تتوافق الأعمدة مع رموز الإدخال.
- الصفوف تتوافق مع الدول.
- الإدخالات تتوافق مع الحالة التالية.
- يتم الإشارة إلى حالة البداية بواسطة سهم بدون مصدر.
- يتم الإشارة إلى حالة القبول بنجمة.
مثال 1:
حل:
جدول الانتقال لـ DFA المحدد هو كما يلي:
قائمة جافا
| الحالة الحالية | الحالة التالية للإدخال 0 | حالة الإدخال التالية 1 |
|---|---|---|
| →س0 | س1 | q2 |
| س1 | س0 | q2 |
| *q2 | q2 | q2 |
توضيح:
- في الجدول أعلاه، يشير العمود الأول إلى جميع الحالات الحالية. تحت العمود 0 و1، يتم عرض الحالات التالية.
- يمكن قراءة الصف الأول من الجدول الانتقالي، عندما تكون الحالة الحالية هي q0، عند الإدخال 0 ستكون الحالة التالية هي q1 وعند الإدخال 1 ستكون الحالة التالية هي q2.
- في الصف الثاني، عندما تكون الحالة الحالية هي q1، عند الإدخال 0، ستكون الحالة التالية هي q0، وعند الإدخال 1 ستكون الحالة التالية هي q2.
- في الصف الثالث، عندما تكون الحالة الحالية هي q2 عند الإدخال 0، ستكون الحالة التالية هي q2، وعند إدخال واحد ستكون الحالة التالية q2.
- يشير السهم المميز بـ q0 إلى أنها حالة البداية وتشير الدائرة المميزة بـ q2 إلى أنها حالة نهائية.
مثال 2:
حل:
لهجة السبات
الجدول الانتقالي لـ NFA المحدد هو كما يلي:
| الحالة الحالية | الحالة التالية للإدخال 0 | حالة الإدخال التالية 1 |
|---|---|---|
| →س0 | س0 | س1 |
| س1 | q1, q2 | q2 |
| q2 | س1 | س3 |
| *س3 | q2 | q2 |
توضيح:
- يمكن قراءة الصف الأول من الجدول الانتقالي، عندما تكون الحالة الحالية هي q0، عند الإدخال 0 ستكون الحالة التالية هي q0 وعند الإدخال 1 ستكون الحالة التالية هي q1.
- في الصف الثاني، عندما تكون الحالة الحالية هي q1، عند الإدخال 0 ستكون الحالة التالية إما q1 أو q2، وعند الإدخال 1 ستكون الحالة التالية هي q2.
- في الصف الثالث، عندما تكون الحالة الحالية هي q2 عند الإدخال 0، ستكون الحالة التالية هي q1، وعند الإدخال الأول ستكون الحالة التالية q3.
- في الصف الرابع، عندما تكون الحالة الحالية هي q3 عند الإدخال 0، ستكون الحالة التالية هي q2، وعند الإدخال الأول ستكون الحالة التالية هي q2.