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

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


קיימים שני סוגים עיקריים: אוטומט סופי דטרמיניסטי (DFA) ואוטומט סופי אי־דטרמיניסטי (NFA).

באוטומט סופי דטרמיניסטי יש קבוצה סופית של מצבים, מצב התחלתי ומספר מצבים מקבלים. פונקציית המעברים קובעת עבור כל מצב q ואות σ מצב יחיד q' שאליו עוברים כאשר קוראים את σ. סדרת המעברים שמתחילה במצב ההתחלתי ומחויבת לפי האותיות שקוראים נקראת ריצה. מילה נקבעת כשמסתיימת ריצה במצב מקבל.

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

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

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


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

באוטומט בוכי (Büchi) קובעים קבוצת מצבים מקבלים. מילה אינסופית מתקבלת אם הריצה עליה מבקרת במצבים מקבלים אינסוף פעמים.

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

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

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


יש שני סוגים עיקריים: דטרמיניסטי (DFA) ולא דטרמיניסטי (NFA).

ב־DFA בכל שלב יש רק צעד יחיד שניתן לעשות. יש מצב התחלתי וכמה מצבים מקבלים. אם אחרי קריאת כל האותיות מגיעים למצב מקבל, המילה מקבלת.

ב־NFA לעתים יש כמה אפשרויות צעד, וגם אפשר לבצע "מעבר־ε". מעבר־ε הוא מעבר שלא קורא אות. מילה מתקבלת אם לפחות דרך אחת מובילה למצב מקבל. אפשר להמיר NFA ל־DFA, כלומר שניהם יכולים לזהות את אותן שפות.


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

באוטומט בוכי (Büchi) המילה מקבלת אם הריצה מבקרת שוב ושוב במצבים מקבלים.

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