• DFA מתייחס לאוטומטים סופיים דטרמיניסטיים. דטרמיניסטי מתייחס לייחודיות של החישוב. האוטומטים הסופיים נקראים אוטומטים סופיים דטרמיניסטיים אם המכונה נקראת מחרוזת קלט סמל אחד בכל פעם.
• ב-DFA, יש רק נתיב אחד לקלט ספציפי מהמצב הנוכחי למצב הבא.
• DFA אינו מקבל את המהלך האפס, כלומר, ה-DFA אינו יכול לשנות מצב ללא תו קלט כלשהו.
• DFA יכול להכיל מספר מצבים סופיים. הוא משמש בניתוח לקסיקלי בקומפיילר.

בתרשים הבא, אנו יכולים לראות שממצב q0 עבור קלט a, יש רק נתיב אחד שהולך ל-q1. באופן דומה, מ-q0, יש רק נתיב אחד לקלט b שעובר ל-q2.

הגדרה רשמית של DFA

DFA הוא אוסף של 5-tuples כמו שתיארנו בהגדרה של FA.

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

ניתן להגדיר את פונקציית המעבר כ:

 δ: Q x ∑→Q 

ייצוג גרפי של DFA

DFA יכול להיות מיוצג על ידי דיגרפים הנקראים דיאגרמת מצב. שבו:

1. המדינה מיוצגת על ידי קודקודים.
2. הקשת המסומנת בתו קלט מציגה את המעברים.
3. המצב ההתחלתי מסומן בחץ.
4. המצב הסופי מסומן במעגל כפול.

דוגמה 1:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} 

פִּתָרוֹן:

תרשים מעבר:

טבלת מעבר:

דוגמה 2:

DFA עם ∑ = {0, 1} מקבל הכל מתחיל ב-0.

פִּתָרוֹן:

הֶסבֵּר:

• בתרשים שלמעלה, אנו יכולים לראות שב-0 נתון כקלט ל-DFA במצב q0, ה-DFA משנה את המצב ל-q1 ותמיד עובר למצב סופי q1 בכניסה מתחילה 0. הוא יכול לקבל 00, 01, 000, 001... .וכו. הוא לא יכול לקבל שום מחרוזת שמתחילה ב-1, כי היא לעולם לא תעבור למצב סופי במחרוזת שמתחילה ב-1.

דוגמה 3:

DFA עם ∑ = {0, 1} מקבל את כל המסתיימות ב-0.

פִּתָרוֹן:

הֶסבֵּר:

בתרשים לעיל, אנו יכולים לראות שבנתון 0 כקלט ל-DFA במצב q0, ה-DFA משנה מצב ל-q1. זה יכול לקבל כל מחרוזת שמסתיימת ב-0 כמו 00, 10, 110, 100... וכו'. זה לא יכול לקבל שום מחרוזת שמסתיימת ב-1, כי היא לעולם לא תעבור למצב הסופי q1 בקלט 1, כך שהמחרוזת המסתיימת ב-1, לא תתקבל או תידחה.