אוטומטים ושפות פורמליות/אוטומט סופי לא דטרמיניסטי: הבדלים בין גרסאות בדף

<math>A=\left\{\Sigma, Q, Q_0q_0, F, \delta\right\}</math>

* <math>\ Q</math> היא [[קבוצה סופית]] של מצבים

* <math>\ Q_0q_0</math> היאהמצב קבוצת המצבים ההתחלתייםההתחלתי של האוטומט (מהםממנו מתחיל החישוב), <math>\ Q_0q_0\subseteqin Q </math>

<math>\ \delta: Q\times (\Sigma\cup\left\{\varepsilon\right\})\rarr P(Q) </math> (לכל מצב ואות קלט או המילה הריקה מותאמת קבוצה של מצבים שאליהם יכול האוטומט לעבור)

השפה שאותה מקבל האוטומט מוגדרת כאוסף המילים עבורן קיים מסלול חישוב של האוטומט שמסתיים במצב מקבל. בניסוח פורמלי, <math>\ L(A)=\left\{w\in\Sigma^*|\delta(Q_0q_0,w)\cap F\ne\emptyset\right\}</math>, כאשר כאן <math>\ \delta</math> היא ההרחבה הטבעית של פונקציית המעברים עבור מילים וקבוצות של מצבים - כלומר קבוצת כלל המצבים מהם ניתן להגיע אם מתחילים במצב <math>q_0</math> וקוראים את הקלט <math>w</math>.