שפה רגולרית

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 הגדרה
2 דוגמאות
3 תכונות מרכזיות של שפות רגולריות
4 ראו גם

[עריכה] הגדרה

אוטומט סופי דטרמיניסטי הוא מערכת הכוללת מספר סופי של מצבים, (וביניהם "מצבי התחלה" ו"מצבי סיום"), וחוקי מעבר ממצב למצב, התלויים בקלט. האוטומט יכול לקרוא בזו אחר זו את האותיות במלה נתונה, ולעבור בין המצבים השונים בהתאם לתוכן המלה, עד שזו מסתיימת. אם האוטומט הגיע באותה עת לאחד ממצבי הסיום, המלה מתקבלת כמלה חוקית; אחרת, היא נדחית. אוסף המלים שהאוטומט A מקבל, (בסימנים, $\ L = L \left( A \right)$ ) נקרא "שפה רגולרית".

את המושג "שפה רגולרית" אפשר להגדיר בדרכים שונות:

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

[עריכה] דוגמאות

הדוגמה הפשוטה ביותר לשפה רגולרית היא השפה הריקה. כיוון שכל אס"ד חסר מצבים מקבלים יתאר אותה.
השפה { $\ \varepsilon$ }, המכילה את המלה הריקה ותו לא, היא רגולרית, (מעל הא"ב $\ a,b,c$ ) מאחר שהאוטומט הבא מקבל אותה (העיגול הכפול מסמן מצב סיום) -

השפה שהמלים החוקיות שלה הן אלו שבהן האות a מופיעה לפחות שלוש פעמים, מתוארת על-ידי האוטומט

לעומת זאת, השפה { $\ a^k b^l | k = l$ } אינה רגולרית, מאחר וזיהוי מילים בשפה תדרוש מהאוטומט "לספור" מספר לא חסום של אותיות - משימה שאינה אפשרית עבור אוטומט סופי, שזכרונו מוגבל.

[עריכה] תכונות מרכזיות של שפות רגולריות

אם $\ L_1$ ו- $\ L_2$ שפות רגולריות, אז האיחוד שלהן (השפה הכוללת את כל המלים שהן חוקיות באחת משתיהן) גם הוא שפה רגולרית. גם השרשור (השפה בעלת המלים $\ w_1w_2$ , לכל $\ w_1\in L_1$ ו- $\ w_2 \in L_2$ ) הוא שפה רגולרית. אם $\ L$ שפה רגולרית, גם השפה הנוצרת על-ידה (שהיא השפה $\ L^*$ שהמלים שלה $\ w_1\dots w_n$ מורכבות מקטעים $\ w_1,\dots,w_n\in L$ ) היא שפה רגולרית.

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

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

ידוע שלכל שפה רגולרית קיים אוטומט יחיד (עד כדי החלפת שמות המצבים), בעל מספר מצבים מינימלי, המתאר אותה. משפט חשוב אחר, של Schulzenberger (מ-1965) מתאר את משפחת השפות המתקבלות מן השפות הסינגלטוניות על-ידי פעולות האיחוד, השרשור והמשלים: אלו הן כולן שפות רגולריות, המתאפיינות בכך שבאוטומט המינימלי המתאר אותן אין מעגלים (למעט, אולי, לולאות באורך 1). פירושו של דבר הוא שהחבורה למחצה הצמודה לאוטומט מקיימת את הזהות $\ x^{n+1}=x^n$ , כאשר n הוא מספר המצבים. משפט זה מספק גם קשר ללוגיקה מתמטית: השפות המתקבלות מפעולות איחוד, שרשור ומשלים, הן השפות שאפשר לתאר באופן פורמלי במסגרת שפה מסדר ראשון. את כל השפות הרגולריות אפשר לתאר במסגרת שפה מסדר שני. קיומה של שפה כדוגמת $\ (aa)^*$ , שהיא רגולרית אבל אינה ניתנת לבניה בעזרת איחוד, שרשור ופעולת המשלים, מוכיח שהיכולת התאורית של שפות מסדר שני חזקה מזו של כל השפות מסדר ראשון.