תורת האוטומטים

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

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

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

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

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

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

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

אוטומטי-\omega[עריכת קוד מקור | עריכה]

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

קיימים מודלים שונים שמגדירים קבלה של מילים אינסופיות. למשל, באוטומט בוקי (Büchi) תנאי הקבלה מגדיר קבוצת מצבים מקבלים, ומילה מתקבלת אם ורק אם היא מבקרת במצב מקבל אינסוף פעמים. באוטומט רבין תנאי הקבלה מורכב מזוגות של קבוצות \{<G_1,B_1>,<G_2,B_2>,\cdots,<G_k,B_k>\} כאשר ריצה היא מקבלת אם קיים זוג <G_i,B_i> שעבורו קבוצת המצבים S שבהם מבקרת הריצה אינסוף פעמים מקיימת S \cap G_i \neq \emptyset ו- S\cap B_i=\emptyset, כלומר הריצה מבקרת אינסוף פעמים במצב מ-G_i ומבקרת רק מספר סופי של פעמים בכל מצבי B_i. מלבד שני מודלים אלו קיימים מודלים רבים נוספים אשר מגדירים את אופן קבלת המילים על ידי האוטומט.

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

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

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