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

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



המתוארת בטבלת מעברים -
-
1 0 δ 





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


