אוטומט סופי

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

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

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

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

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

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

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

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

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

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

ראו גם

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

לקריאה נוספת

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אוטומט סופי34247921Q176452