הצגת המקור של הדף "תורת האוטומטים"

[[קובץ:Automat1.JPG|ממוזער|שמאל|250px| נורה כאוטומט סופי]]
'''[[אוטומט סופי]]''' הוא [[מכונה מופשטת]] בתורת ה[[חישוביות]] ב[[מדעי המחשב]], שהיא בעלת זיכרון מוגבל ומגדירה [[שפה פורמלית]] [[שפה רגולרית|רגולרית]].

== סיווג ==
קיימים שני סוגים של אוטומטים סופיים – [[אוטומט סופי דטרמיניסטי]] (DFA –{{כ}} Deterministic Finite Automaton) ו[[אוטומט סופי לא דטרמיניסטי]] (NFA –{{כ}} Nondeterministic Finite Automaton).

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

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

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

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

== אוטומטי-<math>\omega</math> ==

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

קיימים מודלים שונים שמגדירים קבלה של מילים אינסופיות.
למשל, באוטומט בוקי (Büchi) תנאי הקבלה מגדיר קבוצת מצבים מקבלים, ומילה מתקבלת אם ורק אם היא מבקרת במצב מקבל אינסוף פעמים.
באוטומט [[מיכאל רבין|רבין]] תנאי הקבלה מורכב מזוגות של קבוצות <math>\{\langle G_1,B_1 \rangle,\langle G_2,B_2 \rangle,\cdots,\langle G_k,B_k \rangle\}</math> כאשר ריצה היא מקבלת אם קיים זוג <math>\langle G_i,B_i \rangle</math> שעבורו קבוצת המצבים <math>S</math> שבהם מבקרת הריצה אינסוף פעמים מקיימת
<math>S \cap G_i \neq \emptyset</math>
ו-
<math>S\cap B_i=\emptyset</math>, 
כלומר הריצה מבקרת אינסוף פעמים במצב מ-<math>G_i</math> ומבקרת רק מספר סופי של פעמים בכל מצבי <math>B_i</math>. מלבד שני מודלים אלו קיימים מודלים רבים נוספים אשר מגדירים את אופן קבלת המילים על ידי האוטומט.

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

== ראו גם ==
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}
* [[תורת האוטומטים - מונחים]]
* [[ההיררכיה של חומסקי]]
* [[אוטומט מחסנית]]
* [[מכונת טיורינג]]

== לקריאה נוספת ==
* {{פא"ר|מספר=93|שם הספר=אוטומטים ושפות פורמליות|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}}

{{מדעי המחשב}}
==קישורים חיצוניים==
* {{MathWorld}}
* {{בריטניקה}}
* {{דף שער בספרייה הלאומית|987007541154705171|אוטומטים (תיאוריה)}}

{{בקרת זהויות}}

[[קטגוריה:אוטומטים]]