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

ב[[תורת החישוביות]], '''אוטומט סופי דטרמיניסטי''' (להלן: אס"ד) הוא [[מודל מתמטי]], המגדיר [[שפה פורמלית]]. המודל מורכב מ[[קבוצה סופית|אוסף סופי]] של [[מצב (מדעי המחשב)|מצב]]ים וכְלָלֵי מַעֲבַר ביניהם. בהינתן [[קלט]], הבנוי מסדרה של סמלים (סימנים) מתוך [[אלפבית (שפה פורמלית)|א"ב]] (אוסף כל הסימנים האפשריים) ידוע, מתבצע מעבר סדרתי על הסמלים, ובהתאם, מתבצעים מעברים בין מצבי האוטומט – אחד עבור כל סמל. המצב ההתחלתי ידוע מראש וכל מעבר מוגדר באופן חד-ערכי ויחיד ("דטרמיניסטי") על פי הסמל הבא שנקרא. כאשר נקראים כל הסמלים שבקלט, מתבצעת בדיקה של סוג המצב בו נמצא האוטומט (המצב האחרון שאליו הגיע). אם מדובר ב"מצב מקבל", הקלט נחשב כ"מילה בשפה" של האוטומט, אחרת, הוא נחשב כמילה שאיננה שייכת לשפת האוטומט. 

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

==הגדרה פורמלית==
{{סימון מתמטי}}
אס"ד <math>\ A</math> [[הגדרה (מתמטיקה)|מוגדר]] להיות ה[[N-יה סדורה|חמישייה הסדורה]] הבאה:

<math>A=(\Sigma, Q, q_0, F, \delta)</math>

כאשר:
* <math>\Sigma</math> היא (קבוצת) [[אלפבית (שפה פורמלית)|אלפבית]] הקלט. כל [[איבר (מתמטיקה)|איבר]] בקבוצה זו מכונה "אות".
* <math>Q</math> היא קבוצה סופית של מצבים. כל מצב בקבוצה זו הוא, בהכרח, בדיוק אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
* <math>q_0</math> הוא המצב ההתחלתי של האס"ד (ממנו מתחיל החישוב), <math>q_0 \in Q </math>.
* <math>F</math> היא קבוצת מצבים מקבלים, <math>F \subseteq Q</math>. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה של האס"ד.
* <math>\delta</math> היא [[פונקציית מעברים|פונקציית המעברים]], <math>\delta \colon \Sigma\times Q\rarr Q </math> (לכל מצב ואות קלט [[יחס (תורת הקבוצות)|מותאם]] מצב אחד ויחיד, ולכן, אוטומט זה נקרא [[דטרמיניזם|דטרמיניסטי]]).

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

1. האס"ד מתחיל את פעולתו במצב <math>q_0</math> ומקבל מילת קלט (סופית או ריקה ("[[מחרוזת ריקה (תכנות)|מילה ריקה]]" היא מילה עם 0 אותיות)). 

2. האס"ד בודק האם קיימות אותיות במילה:
* 2א. אם נותרו אותיות נוספות, האס"ד קורא את האות הבאה בסדרה (אות אחת בלבד), עובר למצב חדש, לפי פונקציית המעברים, ובודק שוב אם קיימות אותיות נוספות במילה, שלא נקראו (חוזר לשלב 2).
* 2ב. אם לא נותרו אותיות נוספות לקריאה, האס"ד יסיים את פעולתו: 
** 2ב-1. אם האוטומט נעצר (הגיע) במצב מקבל, המילה תתקבל.
** 2ב-2. אחרת, המילה לא תתקבל.

==דוגמאות לאוטומטים סופיים==
===אוטומט המקבל מילים המכילות מספר זוגי של אפסים===

נתבונן באוטומט <math>A=\left\{\Sigma, Q, q_0, F, \delta\right\}</math> המוגדר כך:

* <math>\Sigma=\left\{0,1\right\} </math>
* <math>Q=\left\{q_0,q_1\right\} </math>
* <math>F=\left\{q_0\right\}</math> 
* <math>\ \delta</math> מתוארת ב[[פונקציית מעברים#טבלת מעברים|טבלת מעברים]]:
:{| border=1 cellpadding=4 cellspacing=0
|-
|- bgcolor="#E0F0E0"
|'''1'''||'''0'''||<math>\delta</math>
|-
|<math>\ q_0</math> || <math>\ q_1</math> || <math>\ q_0</math>
|-
|<math>\ q_1</math> || <math>\ q_0</math> || <math>\ q_1</math>
|-
|}

אס"ד זה ניתן להצגה גם כ[[גרף מכוון|גרף המכוון]] הבא: 

[[קובץ:Even Number of Zeros DFA.png]]

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

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

===אוטומט המקבל מילים המתחילות ברצף 101===
[[קובץ:Automat4.PNG|ממוזער|מרכז|400px| המצב המקבל היחיד הוא Q4 (ב[[ירוק]]), ורק אם הגענו אליו, כל אות נוספת כלשהי שתוקלד/תיקרא לא תשפיע על קביעת האוטומט הסופית בנוגע לשייכות (או אי-שייכות) המילה לשפה, ונישאר באותו מצב – לכן, מתבצע מעבר לולאתי ממצב זה לעצמו, בין אם מגיעה האות <math>\ 0</math> ובין אם מגיעה האות <math>\ 1</math> (כל אותיות ה-א"ב). המצב Q5 ׁ(ב[[סגול]]) מכונה "מצב מלכודת" (כי לא ניתן לצאת ממנו){{הערה|גם מצב Q4 עונה על הגדרה זו, אך מכיוון שהוא מצב מקבל, הוא מכוּנה "מלכודת מקבלת" או "מצב מלכודת מקבל".}} (קרוי גם "מצב סופג"), הזוכר כי הקלט אינו עונה על הציפייה; כלומר, הקלט אינו פותח ברצף "101", ולכן, קליטת אות א"ב נוספת כלשהי אינה משנה דבר.]]

האוטומט המוצג ב[[איור]] דואג לכך שמילות הקלט שיעברו דרכו יתחילו ברצף "101". א"ב האוטומט הוא הספרות 0 ו-1, המצב המקבל הוא מצב Q4 (מיוצג על ידי עיגול כפול), המצב ההתחלתי (המצב שבו מתחיל האוטומט; כלומר, לפני שנקלטה אות כלשהי) הוא המצב Q1, ו-Q5 הוא "מצב מלכודת". אם אוטומט זה היה מופעל על ידי [[מחשב]] פרימיטיבי בעל מקלדת עם הכפתורים 0 ו-1 בלבד ונורה המציינת אם הקלט חוקי (בשפה) או לא, היה האוטומט מתחיל במצב Q1 והנורה הייתה כבויה. אם המשתמש היה מקליד את ה[[מחרוזת (מדעי המחשב)|מחרוזת]] "000", או "100" בהתחלה, קריאה נוספת של כל אות הייתה גורמת למילה (הקלט) לא להיקלט על ידי האוטומט, מאחר שהוא היה מגיע למצב המלכודת Q5. מאידך, אם המשתמש היה מקיש בהתחלה את המחרוזת "101", הנורה הייתה נדלקת, כאינדיקציה לכך שהמילה חוקית בשפה. קריאת אות נוספת (הקשה על הכפתורים 0 או 1 על ידי המשתמש) לא הייתה משנה עובדה זו, והנורה הייתה ממשיכה לדלוק. כל עוד נמצאים במצב שאינו Q4, הנורה כבויה. רק במצב Q4 הנורה דולקת.

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

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

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

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

==הערות שוליים==
{{הערות שוליים}}

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