שאלות נפוצות

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

ב־DFA לכל זוג (מצב, סמל) יש בדיוק מעבר אחד, מה שהופך את הריצה לדטרמיניסטית. ב־NFA יכולים להיות אפס, אחד או מספר מעברים לכל זוג, והוא גם מאפשר מעברי ε (מעברים ללא קריאת קלט). למרות זאת, DFA ו־NFA מזהים בדיוק את אותה מחלקת שפות — השפות הרגולריות.

DFA מזהה בדיוק את השפות הרגולריות: אלו שניתן לתאר בעזרת ביטויים רגולריים או דקדוקים רגולריים. דוגמאות כוללות מחרוזות המכילות תבנית קבועה, מחרוזות באורך זוגי, או מספרים בינאריים המתחלקים במספר שלם נתון. שפות כמו {aⁿbⁿ} או סוגריים מאוזנים אינן רגולריות ולא ניתנות לזיהוי על ידי אף DFA.

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

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

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

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

כן. עבור כל NFA קיים DFA שמזהה את אותה שפה, באמצעות בניית קבוצות החזקה (subset construction). ה־DFA המתקבל עשוי להכיל במקרה הגרוע מספר מצבים אקספוננציאלי, אך השפה המזוהה זהה. שני המודלים מגדירים בדיוק את מחלקת השפות הרגולריות.

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

NFA מקבל מחרוזת אם קיימת לפחות סדרה אחת של מעברים — בעקבות סמלי הקלט וכל מעברי ε — שמובילה ממצב ההתחלה למצב מקבל לאחר קריאת כל הקלט. מספיק שהסתעפות אחת תצליח; כל שאר ההסתעפויות עשויות לדחות או להיתקע.

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

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

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

התווית "a,A/BC" משמעה: קרא קלט "a", שלוף "A" מראש המחסנית, ודחוף "BC" כאשר "B" הופך לראש החדש. דחיפה ריקה (הנכתבת ε) משמעה שליפה בלבד. התו השמאלי ביותר במחרוזת הדחיפה נדחף אחרון, ולכן הוא זה שנשאר בראש.

PDA מזהה את כל השפות חופשיות־ההקשר, המכילות ממש את השפות הרגולריות. דוגמאות קלאסיות הדורשות מחסנית הן {aⁿbⁿ | n ≥ 1} (מספר שווה של a ו־b) וסוגריים מאוזנים. עם זאת, PDA אינו יכול לזהות את כל השפות — {aⁿbⁿcⁿ} למשל דורש מכונת טיורינג.

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

לא. כל שפה המזוהה על ידי DFA או NFA מזוהה גם על ידי PDA (שכן השפות הרגולריות הן תת־קבוצה של השפות חופשיות־ההקשר), אך ההפך אינו נכון. PDA יכול לזהות את {aⁿbⁿ} וסוגריים מאוזנים, שאף DFA או NFA אינם יכולים. המחסנית מעניקה ל־PDA זיכרון רב יותר ממש מהבקרה הסופית של DFA/NFA.

לא — מכונת טיורינג חזקה ממש יותר. למכונת טיורינג יש סרט קריאה/כתיבה לא־חסום שניתן לנוע עליו בשני הכיוונים, בעוד של־PDA יש רק מחסנית (נכנס־אחרון־יוצא־ראשון). שפות כמו {aⁿbⁿcⁿ} מעבר ליכולתו של כל PDA אך כריעות על ידי מכונת טיורינג. מכונות טיורינג יכולות לחשב כל דבר הניתן לחישוב אלגוריתמי; PDA מוגבל לשפות חופשיות־ההקשר.

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

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

מכונת טיורינג רב־סרטית מכילה מספר סרטים בלתי־תלויים, לכל אחד ראש קריאה/כתיבה משלו. מספר סרטים יכול להקל משמעותית על כתיבת תוכניות, אך כל מכונה רב־סרטית ניתנת לסימולציה על ידי מכונה חד־סרטית — כך ששני המודלים מזהים בדיוק את אותה מחלקת שפות.

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

תזת צ'רץ'–טיורינג היא ההשערה שכל פונקציה הניתנת לחישוב על ידי אלגוריתם אפקטיבי ניתנת לחישוב על ידי מכונת טיורינג. זו תזה ולא משפט — לא ניתן להוכיחה פורמלית — אך עשרות שנות מחקר לא מצאו דוגמאות נגד, וכל המודלים הידועים של חישוב כללי שקולים בכוחם.

דקדוק חופשי־הקשר הוא דקדוק פורמלי עם כללי גזירה המחליפים משתנה יחיד במחרוזת של טרמינלים ומשתנים. CFG מתאר שפות חופשיות־הקשר ונמצא בשימוש נרחב להגדרת התחביר של שפות תכנות. הוא בעל כוח ביטוי רב יותר ממש מדקדוקים רגולריים (DFA/NFA).

הצורה הנורמלית של חומסקי היא צורה מוגבלת של CFG שבה כל כלל הוא או A → BC (שני משתנים) או A → a (טרמינל אחד). כל CFG ניתן להמרה ל־CNF בלי לשנות את השפה שהוא מייצר. CNF נדרש עבור אלגוריתם CYK המשמש בסימולטור זה.

אלגוריתם קוק–יאנגר–קסאמי (CYK) הוא אלגוריתם תכנון דינמי המכריע האם מחרוזת שייכת לשפה חופשית־הקשר. הוא ממלא טבלה משולשית בגודל n×n של תת־מחרוזות מלמטה למעלה ורץ בזמן O(n³ · |G|), כאשר n הוא אורך הקלט ו־|G| הוא גודל הדקדוק.

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

CFG מתאר שפות חופשיות־הקשר, המכילות ממש את כל השפות הרגולריות. דוגמאות קלאסיות שאינן רגולריות הן {aⁿbⁿ | n ≥ 1} (מספר שווה של a ו־b), סוגריים מאוזנים וביטויים אריתמטיים. עם זאת, שפות חופשיות־הקשר אינן יכולות לתאר את {aⁿbⁿcⁿ} — זה דורש מודל חזק יותר כמו מכונת טיורינג.