אוטומטים ושפות פורמליות/אוטומט סופי דטרמיניסטי: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 4:
כאמור, אנו דנים רק במכונות ''הכרעה'', כאלו שעל כל קלט עונות "כן" או "לא". כדי להחליט האם המכונה מקבלת את הקלט או דוחה אותו, נסמן מצבים מסויימים כ'''מצבים מקבלים'''. באיור ניתן לראות כי המצב "q" מסומן בעיגול כפול - זהו הסימון המקובל למצב מקבל. כאמור, המכונה משנה את מצבהּ עבור כל אות שבקלט, לכן לאחר סיום עיבוד כלל אותיות הקלט המכונה תהיה במצב מסויים יחיד. אם המצב הזה הוא מצב מקבל - אומרים שהקלט התקבל ע"י המכונה. ואחרת, הקלט נדחה.
למשל, בדוגמא לעיל הקלט "a" מתקבל על-ידי המכונה (כי לאחר עיבוד האות "a" נגיע למצב המקבל q), ואילו הקלט <math>\varepsilon</math> נדחה על-ידי המכונה, כי לאחר עיבודו המכונה נמצאת במצב p שאינו מצב מקבל (עיבוד המילה הריקה - מתחילים במצב p ולא משנים מצב, כי הקלט נגמר...)
== מה מגדיר מכונת מצבים ==
| |||