אוטומט סופי דטרמיניסטי

בתורת החישוביות אוטומט סופי דטרמיניסטי (להלן: אס"ד) הוא מודל מתמטי המגדיר שפה פורמלית. המודל מורכב מאוסף סופי של מצבים וכללי מעבר ביניהם. בהינתן קלט הבנוי מסדרה של סמלים מתוך א"ב ידוע, מתבצע מעבר סידרתי על הסמלים ובמקביל מתבצעים מעברים בין מצבי האוטומט. המצב התחילי ידוע מראש וכל מעבר מוגדר באופן חד ערכי על פי הסמל הבא שנקרא. כאשר נקראות כל אותיות הקלט, מתבצעת בדיקה של סוג המצב בו נמצא האוטמט. אם מדובר ב"מצב מקבל", הקלט נחשב כמילה בשפה של האוטמט אחרת הוא נחשב כמילה שאיננה שייכת לשפת האוטומט.

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

הגדרה פורמלית

אס"ד $\ A$ מוגדר באמצעות -

$A=\left\{\Sigma, Q, q_0, F, \delta\right\}$

כאשר:

• $\ \Sigma$ היא א"ב הקלט
• $\ Q$ היא קבוצה סופית של מצבים
• $\ q_0$ הוא המצב ההתחלתי של האס"ד (ממנו מתחיל החישוב), $\ q_0\isin Q$
• $\ F$ היא קבוצת מצבים מקבלים, $\ F\subseteq Q$. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה של האס"ד.
• $\ \delta$ היא פונקציית המעברים, $\ \delta:\Sigma\times Q\rarr Q$ (לכל מצב ואות קלט מותאם מצב אחד ויחיד, ולכן אוטומט זה נקרא דטרמיניסטי)

אופן פעולת האוטומט

האס"ד קורא את מילת הקלט תוך כדי מעבר בין מצביו השונים ובסיום קריאת המילה מחליט האם היא שייכת לשפה לפי סוג המצב אליו הגיע -

1. האס"ד מתחיל את פעולתו במצב $\ q_0$ ומקבל מילת קלט. (סופית או ריקה)

2. האס"ד בודק האם קיימות אותיות במילה -

• 2א. אם נותרו אותיות נוספות, האס"ד עובר למצב חדש לפי פונקציית המעברים, ובודק שוב אם קיימות אותיות נוספות (חוזר לשלב 2).
• 2ב. אם לא נותרו אותיות נוספות, האס"ד יסיים את פעולתו -
  • 2ב1. אם הגיע למצב מקבל, המילה תתקבל.
  • 2ב2. אחרת, המילה לא תתקבל.

דוגמאות לאוטומטים סופיים

אוטומט המקבל מילים המכילות מספר זוגי של אפסים

נתבונן באוטומט $A=\left\{\Sigma, Q, q_0, F, \delta\right\}$ המוגדר כך -

• $\Sigma=\left\{0,1\right\}$
• $Q=\left\{q_0,q_1\right\}$
• $F=\left\{q_0\right\}$
• $\ \delta$ המתוארת בטבלת מעברים -

1	0	$\delta$
$\ q_0$	$\ q_1$	$\ q_0$
$\ q_1$	$\ q_0$	$\ q_1$

אס"ד זה ניתן להצגה גם כגרף מכוון -

כאשר -

• כל מעגל מייצג מצב, ומעגל כפול מייצג מצב מקבל.
• כל קשת בין שני מצבים מייצגת מעבר בין שני מצבים והאות שעליה מייצגת את הקלט שבעת קריאתו יתבצע המעבר.

ניתן לראות שאס"ד זה עובר ממצב אחד לאחר רק בעת קריאת $\ 0$, וקל לראות (או להוכיח באינדוקציה) שמילה תתקבל אם מס' המופעים של $\ 0$ בה יהיה זוגי.

אוטומט המקבל מילים המתחילות ברצף 101

המצב המקבל הוא Q4 (בירוק) ורק אם הגענו אליו כל אות נוספת שתוקלד לא תשפיע על האוטומט ונישאר באותו מצב - לכן מתבצע מעבר לולאתי ממצב זה אם מגיעה האות 0 או האות 1. המצב Q5 הוא מצב מלכודת (קרוי גם מצב סופג, בסגול) הזוכר כי הקלט אינו עונה על הציפייה, כלומר הקלט אינו פותח ברצף 101 ולכן קליטת תו כלשהו (קריאת אות) אינה משנה דבר.

האוטומט המוצג באיור דואג לכך שמילות הקלט שתעברנה דרכו יתחילו ברצף 101. א"ב האוטומט הן הספרות 0 ו-1, המצב המקבל הוא מצב Q4 (מיוצג על ידי עיגול בתוך עיגול), המצב ההתחלתי (המצב שבו מתחיל האוטומט, כלומר לפני שנקלט תו כלשהו) הוא המצב Q1, ו-Q5 הוא מצב מלכודת. אם אוטומט זה היה מופעל על ידי מחשב פרימיטיבי בעל מקלדת עם הכפתורים 0 ו-1 בלבד ונורה המציינת אם הקלט חוקי או לא, האוטומט היה מתחיל במצב Q1 והנורה הייתה כבויה. אם המשתמש היה מקליד את המחרוזת 000, או 100 בהתחלה, קריאה נוספת של כל תו הייתה גורמת למילה (הקלט) לא להיקלט על ידי האוטומט מאחר שהוא היה מגיע למצב המלכודת Q5. מאידך, אם המשתמש היה מקיש את המחרוזת 101 הנורה הייתה נלקדת כאינדיקציה לכך שהמילה חוקית. קריאת אות נוספת (הקשה על הכפתור 0 או 1 על ידי המשתמש) לא הייתה משנה עובדה זו והנורה הייתה ממשיכה לדלוק. כל עוד נמצאים במצב שאינו Q4 הנורה כבויה ורק במצב זה הנורה דולקת.

ראו גם

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

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 2000 (הספר במיזם פא"ר)