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

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

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

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

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

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