אוטומט סופי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
נורה כאוטומט סופי

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

קיימים שני סוגים של אוטומטים סופיים – אוטומט סופי דטרמיניסטי (DFA –‏ Deterministic Finite Automaton) ואוטומט סופי לא דטרמיניסטי (NFA –‏ Nondeterministic Finite Automaton).

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

אוטומט סופי לא־דטרמיניסטי דומה לאוטומט הדטרמיניסטי, רק שמכל מצב יכולים להיות מספר מסלולים למצב אחר עבור אות קלט, או שאין אף מסלול אפשרי ממצב מסוים עבור אות קלט מסוימת. מבחינה פורמלית, מילה תתקבל אם ורק אם קיים מסלול עבורה מהמצב ההתחלתי עד למצב מקבל כלשהו.

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

שפות המתקבלות על ידי אוטומט סופי נקראות שפות רגולריות ונוצרות על ידי דקדוקים רגולריים.

ניתן להתייחס גם לריצות של אוטומטים סופיים על מילים אינסופיות (סדרות אינסופיות של אותיות מהאלפבית). ניתן להגדיר תנאים שונים להגדרת קבלת מילים במקרה זה. למשל, באוטומט בוקי (Büchi) ריצה תקרא מקבלת אם היא מבקרת במצב מקבל אינסוף פעמים.

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

ראו גם[עריכת קוד מקור | עריכה]