Loading AI tools
מודל חישוב מתמטי מוויקיפדיה, האנציקלופדיה החופשית
בתורת החישוביות במדעי המחשב, אוטומט סופי (או מכונת מצבים) הוא מכונה מופשטת בעלת זיכרון מוגבל בגודלו, המגדירה שפה פורמלית רגולרית.
קיימים שני סוגים של אוטומטים סופיים:
אוטומט סופי דטרמיניסטי מוגדר על ידי החמישייה , כלומר, קבוצה סופית של מצבים המשמשים את האוטומט, והוא עובר בהם החל במצב ההתחלתי , לפי כללים קבועים מראש, במהלך קריאת מילת קלט (מחרוזת תווים/סמלים מהאלפבית ). חלק ממצבי האוטומט הם "מצבים מקבלים" (). אם בסוף קריאת המילה מגיע ועוצר האוטומט במצב מקבל, משמעות הדבר היא שהמילה שייכת לשפה שהוא מגדיר; אחרת, המילה אינה שייכת לשפה.
הכללים למעבר ממצב למצב מוגדרים על ידי פונקציית מעברים (), שמגדירה עבור כל מצב ואות מצב יחיד (ייתכן ש ), אליו עובר האוטומט, כאשר הוא נמצא במצב והאות שהוא קרא מן הקלט היא .
אוטומט סופי לא־דטרמיניסטי מוגדר באופן דומה לאוטומט הדטרמיניסטי, על ידי החמישייה . בשונה מקודמו, במקום מצב התחלתי ישנה קבוצת מצבים התחלתיים . כמו כן, מכל מצב יכולים להיות מספר מעברים למצבים אחרים עבור אותה אות קלט; וייתכן אף מסלול עבור קלט ריק - כלומר, שינוי מצב מבלי לקרוא דבר - קשת כזו נקראת "מעבר-". ישנו גם מצב בו לא הוגדר אף מסלול אפשרי ממצב מסוים עבור אות קלט מסוימת (מוסכם שבמקרה זה קריאת אות זו מהקלט תוביל לבור דוחה, כלומר מצב המכוּנה , שהמעברים היחידים ממנו הם לעצמו, ואיננו מצב מקבל).
מבחינה פורמלית, באוטומט כזה, מילה תתקבל אם ורק אם קיים עבורה (עבור קריאה מלאה שלה) מסלול חוקי ממצב התחלתי כלשהו למצב מקבל כלשהו.
ניתן להוכיח, כי כל אוטומט סופי לא־דטרמיניסטי שקול לאוטומט סופי דטרמיניסטי. כלומר, היעדר הדטרמיניזם אינו מוסיף לכוחו החישובי של האוטומט הסופי (בשונה מאוטומט מחסנית, לדוגמה). לפיכך, שפה היא רגולרית אם ורק אם קיים עבורה אוטומט סופי לא-דטרמיניסטי, שזה מתקיים אם ורק אם קיים עבורה אוטומט סופי דטרמיניסטי.
שפות המתקבלות על ידי אוטומט סופי נקראות שפות רגולריות ונוצרות על ידי דקדוקים רגולריים.
שפות אלה הן קבוצה 'פשוטה' יחסית מתוך כלל השפות חסרות ההקשר, ומסתפקות בזיכרון סופי לצורך יצירת השפה. כל שפה רגולרית היא גם חסרת-הקשר, כלומר, ניתן לבטאה על ידי דקדוק חסר הקשר במקום על ידי אוטומט סופי; אך לא כל שפה חסרת-הקשר היא רגולרית. דרך קלה להבחין בכך ששפה אינה רגולרית היא על ידי שימוש בלמת הניפוח לשפות רגולריות. בשל פשטותן, שפות רגולריות סגורות תחת פעולת חיתוך, לעומת שפות חסרות-הקשר שאינן סגורות לחיתוך.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.