תורת האוטומטים

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

נורה כאוטומט סופי

סיווג

קיימים שני סוגים של אוטומטים סופיים – אוטומט סופי דטרמיניסטי (DFA –‏ Deterministic Finite Automaton) ואוטומט סופי לא דטרמיניסטי (NFA –‏ Nondeterministic Finite Automaton).

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

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

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

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

אוטומטי-$\omega$

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

קיימים מודלים שונים שמגדירים קבלה של מילים אינסופיות. למשל, באוטומט בוקי (Büchi) תנאי הקבלה מגדיר קבוצת מצבים מקבלים, ומילה מתקבלת אם ורק אם היא מבקרת במצב מקבל אינסוף פעמים. באוטומט רבין תנאי הקבלה מורכב מזוגות של קבוצות $\{\langle G_{1},B_{1}\rangle ,\langle G_{2},B_{2}\rangle ,\cdots ,\langle G_{k},B_{k}\rangle \}$ כאשר ריצה היא מקבלת אם קיים זוג $\langle G_{i},B_{i}\rangle$ שעבורו קבוצת המצבים $S$ שבהם מבקרת הריצה אינסוף פעמים מקיימת $S\cap G_{i}\neq \emptyset$ ו- $S\cap B_{i}=\emptyset$, כלומר הריצה מבקרת אינסוף פעמים במצב מ-$G_{i}$ ומבקרת רק מספר סופי של פעמים בכל מצבי $B_{i}$. מלבד שני מודלים אלו קיימים מודלים רבים נוספים אשר מגדירים את אופן קבלת המילים על ידי האוטומט.

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

ראו גם

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

לקריאה נוספת

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

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

• תורת האוטומטים, באתר MathWorld (באנגלית)
• תורת האוטומטים, באתר אנציקלופדיה בריטניקה (באנגלית)
• אוטומטים (תיאוריה), דף שער בספרייה הלאומית