אוטומטים ושפות פורמליות/אוטומט סופי דטרמיניסטי: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
פורמלית
שורה 1:
המודל הראשון שנעסוק בו, הוא '''אוטומט סופי'''. זו היא "מכונת מצבים": בהפעלת המכונה היא מתחילה במצב מסויים, ובמהלך פעולתה היא משנה את המצב הנוכחי בהתאם לקלט.
[[קובץ:FA regexp accept singlesymbol.svg|שמאל|ממוזער|250px|דוגמא לאוטומטלמכונת סופימצבים פשוטפשוטה. המכונה מתחילה במצב "p" ואם מתקבל הקלט a היא עוברת למצב "q".]]
כאמור, אנו דנים רק במכונות ''הכרעה'', כאלו שעל כל קלט עונות "כן" או "לא". כדי להחליט האם המכונה מקבלת את הקלט או דוחה אותו, נסמן מצבים מסויימים כ'''מצבים מקבלים'''. באיור ניתן לראות כי המצב "q" מסומן בעיגול כפול - זהו הסימון המקובל למצב מקבל. כאמור, המכונה משנה את מצבהּ עבור כל אות שבקלט, לכן לאחר סיום עיבוד כלל אותיות הקלט המכונה תהיה במצב מסויים יחיד. אם המצב הזה הוא מצב מקבל - אומרים שהקלט התקבל ע"י המכונה. ואחרת, הקלט נדחה.
 
שורה 27:
<center><math>\delta: Q\times \Sigma \to Q</math></center>
[[קובץ:DFAexample.svg|שמאל|ממוזער|250px|דוגמא לאוטומט סופי.]]
במילים: לכל מצב ואות מהאלפבית מוגדר מצב יחיד אליו המכונה עוברת. הדוגמא שלעיל אינה מקיימת את התנאי הנ"ל - נשים לב שאם אנחנו במצב q ומתקבלת האות "a" המכונה לא יודעת מה לעשות, כי <math>\delta(q,a)</math> אינו מוגדר. להלן דוגמא קצת יותר מורכבת, של מכונה בה בכל מצב מוגדר מעבר לכל אות אפשרית, והמעבר הוא יחיד. מכל מצב יוצאים שני חיצים: אחד עבור "0" ושני עבור "1", מכיוון שהאלפבית הוא האלפבית הבינארי.
 
=== הגדרה פורמלית ===
נסכם את תכונות האוטומט הסופי שראינו לעיל, על-ידי ההגדרה הפורמלית. '''אוטומט סופי''' <math>M</math> הינו החמישייה
<center><math>M=(Q,\Sigma,q_0,F,\delta)</math></center>
 
* <math>Q</math> קבוצת המצבים
* <math>\Sigma</math> - האלפבית
* <math>q_0</math> - מצב התחלתי
* <math>F\subseteq Q</math> - קבוצת המצבים המקבלים (מצבים סופיים)
* <math>\delta: Q\times \Sigma \to Q</math> - פונקציית המעברים