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

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

בתורת החישוביות, אוטומט סופי דטרמיניסטי (להלן: אס"ד) הוא מודל מתמטי, המגדיר שפה פורמלית. המודל מורכב מאוסף סופי של מצבים וכְלָלֵי מַעֲבַר ביניהם. בהינתן קלט, הבנוי מסדרה של סמלים (סימנים) מתוך א"ב (אוסף כל הסימנים האפשריים) ידוע, מתבצע מעבר סדרתי על הסמלים, ובהתאם, מתבצעים מעברים בין מצבי האוטומט – אחד עבור כל סמל. המצב ההתחלתי ידוע מראש וכל מעבר מוגדר באופן חד-ערכי ויחיד ("דטרמיניסטי") על פי הסמל הבא שנקרא. כאשר נקראים כל הסמלים שבקלט, מתבצעת בדיקה של סוג המצב בו נמצא האוטמט (המצב האחרון שאליו הגיע). אם מדובר ב"מצב מקבל", הקלט נחשב כ"מילה בשפה" של האוטומט, אחרת, הוא נחשב כמילה שאיננה שייכת לשפת האוטומט.

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

הגדרה פורמלית

קובץ:Nuvola apps edu mathematics blue-p.svg

בערך זה
נעשה שימוש
בסימנים מוסכמים
מתחום המתמטיקה.
להבהרת הסימנים
ראו סימון מתמטי.


אס"ד הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ A} מוגדר להיות החמישייה הסדורה הבאה:

כאשר:

  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \Sigma} היא (קבוצת) א"ב הקלט. כל איבר בקבוצה זו מכונה "אות".
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ Q} היא קבוצה סופית של מצבים. כל מצב בקבוצה זו הוא, בהכרח, בדיוק אחד מהשניים: "מצב מקבל" או "מצב לא מקבל".
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0} הוא המצב ההתחלתי של האס"ד (ממנו מתחיל החישוב), הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0\isin Q } .
  • היא קבוצת מצבים מקבלים, . מצב מקבל הוא מצב שמסמן שהאוטומט מחזיר תשובה חיובית. כלומר: אם בסוף הקלט האוטומט נמצא במצב מקבל, זה אומר שהקלט הוא מילה בשפה של האס"ד.
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \delta} היא פונקציית המעברים, (לכל מצב ואות קלט מותאם מצב אחד ויחיד, ולכן, אוטומט זה נקרא דטרמיניסטי).

אופן פעולת האוטומט

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

1. האס"ד מתחיל את פעולתו במצב הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0} ומקבל מילת קלט (סופית או ריקה ("מילה ריקה" היא מילה עם 0 אותיות)).

2. האס"ד בודק האם קיימות אותיות במילה:

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

דוגמאות לאוטומטים סופיים

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

נתבונן באוטומט הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A=\left\{\Sigma, Q, q_0, F, \delta\right\}} המוגדר כך:

  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \Sigma=\left\{0,1\right\} }
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle Q=\left\{q_0,q_1\right\} }
  • הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ \delta} מתוארת בטבלת מעברים:
1 0 הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \delta}
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_1} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0}
הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_1} הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ q_0}

אס"ד זה ניתן להצגה גם כגרף המכוון הבא:

Even Number of Zeros DFA.png

כאשר:

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

ניתן לראות שאס"ד זה עובר ממצב אחד לאחר רק בעת קריאת הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 0} , וקל לראות (או להוכיח באינדוקציה), שמילה תתקבל אם ורק אם מספר המופעים של הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 0} בה יהיה זוגי.

אוטומט המקבל מילים המתחילות ברצף 101

שגיאה ביצירת תמונה ממוזערת:
המצב המקבל היחיד הוא Q4 (בירוק), ורק אם הגענו אליו, כל אות נוספת כלשהי שתוקלד/תיקרא לא תשפיע על קביעת האוטומט הסופית בנוגע לשייכות (או אי-שייכות) המילה לשפה, ונישאר באותו מצב – לכן, מתבצע מעבר לולאתי ממצב זה לעצמו, בין אם מגיעה האות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 0} ובין אם מגיעה האות הפענוח נכשל (MathML עם גיבוי SVG או PNG (מומלץ לדפדפנים מודרניים ולכלי נגישות): תגובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \ 1} (כל אותיות ה-א"ב). המצב Q5 ׁ(בסגול) מכונה "מצב מלכודת" (כי לא ניתן לצאת ממנו)[1] (קרוי גם "מצב סופג"), הזוכר כי הקלט אינו עונה על הציפייה; כלומר, הקלט אינו פותח ברצף "101", ולכן, קליטת אות א"ב נוספת כלשהי אינה משנה דבר.

האוטומט המוצג באיור דואג לכך, שמילות הקלט שיעברו דרכו יתחילו ברצף "101". א"ב האוטומט הן הספרות 0 ו-1, המצב המקבל הוא מצב Q4 (מיוצג על ידי עיגול כפול), המצב ההתחלתי (המצב שבו מתחיל האוטומט; כלומר, לפני שנקלטה אות כלשהי) הוא המצב Q1, ו-Q5 הוא "מצב מלכודת". אם אוטומט זה היה מופעל על ידי מחשב פרימיטיבי בעל מקלדת עם הכפתורים 0 ו-1 בלבד ונורה המציינת אם הקלט חוקי (בשפה) או לא, האוטומט היה מתחיל במצב Q1 והנורה הייתה כבויה. אם המשתמש היה מקליד את המחרוזת "000", או "100" בהתחלה, קריאה נוספת של כל אות הייתה גורמת למילה (הקלט) לא להיקלט על ידי האוטומט, מאחר שהוא היה מגיע למצב המלכודת Q5. מאידך, אם המשתמש היה מקיש בהתחלה את המחרוזת "101", הנורה הייתה נדלקת, כאינדיקציה לכך שהמילה חוקית (בשפה). קריאת אות נוספת (הקשה על הכפתורים 0 או 1 על ידי המשתמש) לא הייתה משנה עובדה זו, והנורה הייתה ממשיכה לדלוק. כל עוד נמצאים במצב שאינו Q4, הנורה כבויה. רק במצב Q4 הנורה דולקת.

ראו גם

לקריאה נוספת

הערות שוליים

  1. ^ גם מצב Q4 עונה על הגדרה זו, אך מכיוון שהוא מצב מקבל, הוא מכוּנה "מלכודת מקבלת" או "מצב מלכודת מקבל".