אוטומט סופי

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

מנגנון ממשק מתג להדלקה וכיבוי של נורה מתואר כאוטומט סופי (בייצוגו כגרף מכוון).

הגדרה

קיימים שני סוגים של אוטומטים סופיים:

• אוטומט סופי דטרמיניסטי – ‏אס"ד (DFA –‏ Deterministic Finite Automaton)
• אוטומט סופי לא דטרמיניסטי – ‏אסל"ד (NFA –‏ Nondeterministic Finite Automaton)

אוטומט סופי דטרמיניסטי מוגדר על ידי החמישייה $A=(Q,q_{0},\Sigma ,\delta ,F)$, כלומר, קבוצה סופית $Q$ של מצבים המשמשים את האוטומט, והוא עובר בהם החל במצב ההתחלתי $q_{0}$, לפי כללים קבועים מראש, במהלך קריאת מילת קלט (מחרוזת תווים/סמלים מהאלפבית $\Sigma$). חלק ממצבי האוטומט הם "מצבים מקבלים" ($F$). אם בסוף קריאת המילה מגיע ועוצר האוטומט במצב מקבל, משמעות הדבר היא שהמילה שייכת לשפה שהוא מגדיר; אחרת, המילה אינה שייכת לשפה.

הכללים למעבר ממצב למצב מוגדרים על ידי פונקציית מעברים ($\delta$), שמגדירה עבור כל מצב $q$ ואות $\sigma$ מצב יחיד $q'$ (ייתכן ש $q'=q$), אליו עובר האוטומט, כאשר הוא נמצא במצב $q$ והאות שהוא קרא מן הקלט היא $\sigma$.

אוטומט סופי לא־דטרמיניסטי מוגדר באופן דומה לאוטומט הדטרמיניסטי, על ידי החמישייה $N=(Q,Q_{0},\Sigma ,\delta ,F)$. בשונה מקודמו, במקום מצב התחלתי $q_{0}$ ישנה קבוצת מצבים התחלתיים $Q_{0}$. כמו כן, מכל מצב יכולים להיות מספר מעברים למצבים אחרים עבור אותה אות קלט; וייתכן אף מסלול עבור קלט ריק - כלומר, שינוי מצב מבלי לקרוא דבר - קשת כזו נקראת "מעבר-$\varepsilon$". ישנו גם מצב בו לא הוגדר אף מסלול אפשרי ממצב מסוים עבור אות קלט מסוימת (מוסכם שבמקרה זה קריאת אות זו מהקלט תוביל לבור דוחה, כלומר מצב המכוּנה $q_{rej}$, שהמעברים היחידים ממנו הם לעצמו, ואיננו מצב מקבל).

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

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

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

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

להרחבה

• בנוסף למודלים הנזכרים לעיל, המזהים שפות רגולריות - דקדוק רגולרי, אוטומט סופי דטרמיניסטי ואי-דטרמיניסטי; משפט מייהיל-נרוד מספק לנו מודל חישובי נוסף המזהה אם שפה היא רגולרית אם לאו: שפה $L$ היא רגולרית אם ורק אם היא בעלת מספר סופי של מחלקות שקילות מייהיל-נרוד.

• ניתן להתייחס גם לריצות של אוטומטים סופיים על מילים אינסופיות (סדרות אינסופיות של אותיות מהאלפבית). ניתן להגדיר תנאים שונים לקבלת מילים, במקרה זה. למשל, באוטומט בוקי (Büchi) ריצה תיקרא מקבלת, אם היא מבקרת במצב מקבל אינסוף פעמים.

• נציין כי המילה סופי בשמו של האוטומט מציינת שמספר המצבים באוטומט הוא סופי. אוטומט בעל מספר מצבים אינסופי יגרום למודל להיות חזק יותר ממכונת טיורינג, ולמעשה – כל יכול מבחינה חישובית.^{[דרושה הבהרה]}

ראו גם

• תורת האוטומטים - מונחים
• ההיררכיה של חומסקי
• אוטומט מחסנית
• מכונת טיורינג
• שפה רקורסיבית

לקריאה נוספת

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

קישורים חיצוניים

• אוטומטים סופיים ושפות רגולריות, בבלוג "לא מדויק" של גדי אלכסנדרוביץ', 30 באוגוסט 2009