אוטומטים ושפות פורמליות/אוטומט סופי דטרמיניסטי

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

דוגמא למכונת מצבים פשוטה. המכונה מתחילה במצב "p" ואם מתקבל הקלט a היא עוברת למצב "q".

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

למשל, בדוגמא לעיל הקלט "a" מתקבל על-ידי המכונה (כי לאחר עיבוד האות "a" נגיע למצב המקבל q), ואילו הקלט $\varepsilon$ נדחה על-ידי המכונה, כי לאחר עיבודו המכונה נמצאת במצב p שאינו מצב מקבל (עיבוד המילה הריקה - מתחילים במצב p ולא משנים מצב, כי הקלט נגמר...)

מה מגדיר מכונת מצבים

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

• קבוצת מצבים - הקבוצה שמכילה את כל המצבים האפשריים של המכונה. מסומנת לרוב ב-$Q$.
• אלפבית - קבוצת האותיות שהמכונה מכירה. מסומנת לרוב ב-$\Sigma$
• מצב התחלתי - המצב שבו מתחילה המכונה. מסומן כ-$q_{0}$
• מצבים מקבלים - קבוצת המצבים שסיום עיבוד הקלט בהם מסמל "קבלה" של הקלט. נקראים גם מצבים סופיים, ומסומנים ב$F$. נשים לב שזוהי תת-קבוצה של כלל מצבי המכונה, כלומר $F\subseteq Q$

בדוגמא לעיל:

• $Q=\{p,q\}$
• $\Sigma =\{a\}$
• $q_{0}=p$
• $F=\{q\}$

האם כלל האלמנטים מוגדרים כעת? מה עדיין חסר?

- ה"חיצים", מעברי המכונה לכל קלט וקלט. כיצד ניתן להגדיר את המעברים הללו בצורה מתמטית?

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

$\delta :Q\times \Sigma \to Q$

דוגמא לאוטומט סופי.

במילים: לכל מצב ואות מהאלפבית מוגדר מצב יחיד אליו המכונה עוברת. הדוגמא שלעיל אינה מקיימת את התנאי הנ"ל - נשים לב שאם אנחנו במצב q ומתקבלת האות "a" המכונה לא יודעת מה לעשות, כי $\delta (q,a)$ אינו מוגדר. להלן דוגמא קצת יותר מורכבת, של מכונה בה בכל מצב מוגדר מעבר לכל אות אפשרית, והמעבר הוא יחיד. מכל מצב יוצאים שני חיצים: אחד עבור "0" ושני עבור "1", מכיוון שהאלפבית הוא האלפבית הבינארי.

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

נסכם את תכונות האוטומט הסופי שראינו לעיל, על-ידי ההגדרה הפורמלית. אוטומט סופי $M$ הינו החמישייה

$M=(Q,\Sigma ,q_{0},F,\delta )$

• $Q$ קבוצת המצבים
• $\Sigma$ - האלפבית
• $q_{0}$ - מצב התחלתי
• $F\subseteq Q$ - קבוצת המצבים המקבלים (מצבים סופיים)
• $\delta :Q\times \Sigma \to Q$ - פונקציית המעברים

דוגמא לתכנון אוטומט סופי

נניח כי האלפבית הינו אונרי, כלומר $\Sigma =\{1\}$ ונרצה לתכנן אוטומט המקבל את כל המילים שאורכן הוא כפולה של 3, כלומר אוטומט עבור השפה $L=\{\varepsilon ,111,111111,\ldots \}$ או באופן פורמלי

$L=\{x\in \{1\}^{*}:|x|\mod 3=0\}$

אוטומט סופי עבור השפה האונרית שאורך מילותיה כפולה שלמה של 3.

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

נשים לב שאורכה של המילה הריקה הוא 0, ואורך זה הוא כפולה של שלוש, לכן המצב הראשון (המסמל שארית 0), יהיה מצב מקבל.

תרגיל : תכננו אוטומט סופי מעל האלפבית הבינארי המקבל את כל המחרוזות המייצגות מספר שמתחלק ב-3. ניתן להניח שהמילה הריקה שקולה למספר 0.
(רמז) הוספת 0 למספר בינארי מימינו מכפילה את המספר, והוספת 1 מכפילה ומסיפה 1.

הפרק הקודם: שפות פורמליות

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

הפרק הבא: אוטומט סופי לא דטרמיניסטי