אוטומט סופי דטרמיניסטי

מתוך ויקיפדיה, האנציקלופדיה החופשית

אוטומט סופי דטרמיניסטי (להלן: "אוטומט") הוא מודל מתמטי המגדיר שפה רגולרית.

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

תוכן עניינים

[עריכה] הגדרה פורמלית

אוטומט \ A מוגדר באמצעות -

A=\left\{\Sigma, Q, q_0, F, \delta\right\}

כאשר:

  • \ \Sigma היא א"ב הקלט
  • \ Q היא קבוצה סופית של מצבים
  • \ q_0 הוא המצב ההתחלתי של האוטומט (ממנו מתחיל החישוב), \ q_0\isin Q
  • \ F היא קבוצת מצבים מקבלים, \ F\subseteq Q. מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה של האוטומט.
  • \ \delta היא פונקציית המעברים, \ \delta:\Sigma\times Q\rarr Q (לכל מצב ואות קלט מותאם מצב אחד ויחיד, ולכן אוטומט זה נקרא דטרמיניסטי)

[עריכה] אופן פעולת האוטומט

האוטומט קורא את מילת הקלט תוך כדי מעבר בין מצביו השונים ובסיום קריאת המילה מחליט האם היא שייכת לשפה לפי סוג המצב אליו הגיע -

1. האוטומט מתחיל את פעולתו במצב \ q_0 ומקבל מילת קלט. (סופית או ריקה)

2. האוטומט בודק האם קיימות אותיות במילה -

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

[עריכה] דוגמה לאוטומט

[עריכה] אוטומט המקבל מילים המכילות מספר זוגי של אפסים

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

  • \Sigma=\left\{0,1\right\}
  • Q=\left\{q_0,q_1\right\}
  • F=\left\{q_0\right\}
  • \ \delta המתוארת בטבלת מעברים -
1 0 δ
\ q_0 \ q_1 \ q_0
\ q_1 \ q_0 \ q_1

אוטומט זה ניתן להצגה גם כגרף מכוון -

תמונה:Even Number of Zeros DFA.png

כאשר -

  • כל מעגל מייצג מצב, ומעגל כפול מייצג מצב מקבל.
  • כל קשת בין שני מצבים מייצגת מעבר בין שני מצבים והאות שעליה מייצגת את הקלט שבעת קריאתו יתבצע המעבר.


ניתן לראות שאוטומט זה עובר ממצב אחד לאחר רק בעת קריאת \ 0, וקל לראות (או להוכיח באינדוקציה) שמילה תתקבל אםם מס' המופעים של \ 0 בה יהיה זוגי.

[עריכה] ראו גם

[עריכה] לקריאה נוספת

שפות אחרות