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

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

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

'''אוטומט סופי דטרמיניסטי''' מוגדר על ידי החמישייה <math>A=(Q, q_0, \Sigma, \delta, F)</math>, כלומר, [[קבוצה סופית]] <math>Q</math> של [[מצב (מדעי המחשב)|מצב]]ים המשמשים את האוטומט, והוא עובר בהם החל במצב ההתחלתי <math>q_0</math>, לפי כללים קבועים מראש, במהלך קריאת מילת קלט ([[מחרוזת (מדעי המחשב)|מחרוזת]] תווים/סמלים מה[[אלפבית (שפה פורמלית)|אלפבית]] <math>\Sigma</math>). חלק ממצבי האוטומט הם "מצבים מקבלים" (<math>F</math>). אם בסוף קריאת המילה מגיע ועוצר האוטומט במצב מקבל, משמעות הדבר היא שהמילה שייכת לשפה שהוא מגדיר; אחרת, המילה אינה שייכת לשפה.

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

'''אוטומט סופי לא־דטרמיניסטי''' מוגדר באופן דומה לאוטומט הדטרמיניסטי, על ידי החמישייה <math>N=(Q, Q_0, \Sigma, \delta, F)</math>. בשונה מקודמו, במקום מצב התחלתי <math>q_0</math> ישנה קבוצת מצבים התחלתיים <math>Q_0</math>. כמו כן, מכל מצב יכולים להיות מספר מעברים למצבים אחרים עבור אותה אות קלט; וייתכן אף מסלול עבור קלט ריק - כלומר, שינוי מצב מבלי לקרוא דבר - קשת כזו נקראת "מעבר-<math>\varepsilon</math>". ישנו גם מצב בו לא הוגדר אף מסלול אפשרי ממצב מסוים עבור אות קלט מסוימת ([[קונבנציה|מוסכם]] שבמקרה זה קריאת אות זו מהקלט תוביל ל[[בור דוחה]], כלומר מצב המכוּנה <math>q_{rej}</math>, שהמעברים היחידים ממנו הם לעצמו, ואיננו מצב מקבל).

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

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

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

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

==להרחבה==
* בנוסף למודלים הנזכרים לעיל, המזהים שפות רגולריות - דקדוק רגולרי, אוטומט סופי דטרמיניסטי ואי-דטרמיניסטי; [[משפט מייהיל-נרוד]] מספק לנו מודל חישובי נוסף המזהה אם שפה היא רגולרית אם לאו: שפה <math>L</math> היא רגולרית אם ורק אם היא בעלת מספר סופי של [[מחלקות שקילות]] מייהיל-נרוד.

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

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

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

==לקריאה נוספת==
* {{פא"ר|מספר=418|שם הספר=אוטומטים ושפות פורמליות א|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000|גוגל=3paJMQ-S6CYC&hl}}
* {{פא"ר|מספר=419|שם הספר=אוטומטים ושפות פורמליות ב|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000|גוגל=xLDP7O1oRr8C}}

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

* [https://gadial.net/2009/08/30/finite_automata_and_regular_languages/ אוטומטים סופיים ושפות רגולריות], בבלוג "לא מדויק" של גדי אלכסנדרוביץ', 30 באוגוסט 2009

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

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