שפה רגולרית

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

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

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

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

יש גם משפט של Schulzenberger שמתאר תת-משפחה המתקבלת מאיחוד, שרשור ומשלים: בשפות האלה האוטומט המינימלי כמעט ללא מעגלים. המשפט מקשר גם לטיעונים לוגיים: חזקת התיאור הלוגי של השפות משתנה לפי האם משתמשים ב'חזרה' או לא. הדוגמה (aa)* מראה ששפה יכולה להיות רגולרית אך לא ניתנת לבניה רק מהפעולות של איחוד, שרשור ומשלים.

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

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

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

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

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