תורת האוטומטים - מונחים

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

מושגי יסוד

• א"ב פורמלי: קבוצה סופית של סימנים ("אותיות").
• מילה פורמלית: סדרה סופית של אותיות השייכות לא"ב $\Sigma$ נתון.
• המילה הריקה: מילה שאורכה $0$. נהוג לסמן את מילה זו על ידי $\varepsilon$.
• שפה פורמלית: קבוצת מילים פורמליות.

פעולות על מילים

• אורך של מילה: האורך של מילה שווה למספר האותיות שבה. אורכה של מילה $w$ מסומן ב-$|w|$.
• מס' מופעי אות במילה: מספר מופעי האות $\sigma$ במילה $w$ מסומן ב-$\#_{\sigma }(w)$.
• היפוך מילים: תהי $w={\sigma }_{1}{\sigma }_{2}...{\sigma }_{n}$. היפוכה מסומן ב-$w^{R}$ ומקיים $w^{R}={\sigma }_{n}{\sigma }_{n-1}...{\sigma }_{1}$.
• שרשור מילים: תהיינה שתי מילים $w,z$ כך ש$w={w}_{1}{w}_{2}...{w}_{n},z={z}_{1}{z}_{2}...{z}_{n}$. שרשורן מסומן על ידי $w\cdot z$ או $wz$ ומוגדר כ-${w}_{1}{w}_{2}...{w}_{n}{z}_{1}{z}_{2}...{z}_{n}$.
• חזקה של מילה: $w^{n}$ מוגדרת רקורסיבית כשרשור של $w$ לעצמה $n$ פעמים: $w^{n}={\begin{cases}\varepsilon ,&n=0\\w^{n-1}w,&n>0\end{cases}}$.

פעולות על שפות

• איחוד/חיתוך/השלמה: פעולות אלו זהות לפעולות איחוד חיתוך והשלמה מתורת הקבוצות, רק שאלו פועלות על שפות (כאשר העולם הוא $\Sigma ^{*}$).
• שרשור שפות: שרשור של שתי שפות מוגדר כקבוצת כל המילים הנוצרות משרשור מילה אחת מהשפה הראשונה ומילה אחת מהשנייה. כלומר, יהיו $L_{1},L_{2}$ שפות, שרשורן מסומן ב-$L_{1}L_{2}$ ומקיים $L_{1}L_{2}=\{wv\mid w\in L_{1}\wedge v\in L_{2}\}$.
• חזקה של שפה: החזקה ה-$n$-ית של שפה מוגדרת כשפת כל המילים הנוצרות על ידי שרשור של $n$ מילים מאותה שפה. כלומר, תהי $L$ שפה פורמלית. חזקתה מוגדרת כך: $\ L^{0}=\{\varepsilon \}$ולכל $n>0$ מתקיים $L^{n}=LL^{n-1}$. כלומר, $L^{n}={\begin{cases}\{\varepsilon \},&n=0\\L^{n-1}L,&n>0\end{cases}}$.
• סגור קלין: סגור קלין של שפה $L$ מסומן ב-$L^{*}$ ומוגדר כך: $L^{*}=\bigcup _{i\geq 0}^{\infty }L^{i}$.
• סגור חיובי: הסגור החיובי של שפה $\ L$ מוגדר בדומה לסגור קלין שלה. הוא מסומן ב-$L^{+}$ ומוגדר כך: $L^{+}=\bigcup _{i>0}^{\infty }L^{i}$.

ההיררכיה של חומסקי

ההיררכיה של חומסקי מחלקת את השפות הפורמליות לארבעה סוגים לפי הדקדוקים היוצרים אותן (כל אחד מהדקדוקים בהיררכיה מוגבל יותר מאלו שמעליו):

• דקדוקים בלתי מוגבלים
• דקדוקים תלויי הקשר
• דקדוקים חופשיי הקשר
• דקדוקים רגולריים

דרכים להצגת שפה פורמלית

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

משפטים

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

לקריאה נוספת

• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות א, האוניברסיטה הפתוחה, 2000
• שמואל זקס ונסים פרנסיז, ‏אוטומטים ושפות פורמליות ב, האוניברסיטה הפתוחה, 2000