Loading AI tools
שפה פורמלית שאפשר לתאר על ידי אוטומט סופי מוויקיפדיה, האנציקלופדיה החופשית
בתורת השפות הפורמליות, שפה רגולרית היא שפה פורמלית שאפשר לתאר על ידי אוטומט סופי, האמור לקבוע לגבי מילה נתונה אם היא שייכת לשפה אם לאו. משפחת השפות הרגולריות היא המשפחה הראשונה בהיררכיית השפות של חומסקי.
אוטומט סופי דטרמיניסטי הוא מערכת הכוללת מספר סופי של מצבים וחוקי מעבר ממצב למצב, התלויים בקלט. אחד המצבים מוגדר כמצב ההתחלה. חלק מהמצבים מוגדרים כמצבים מקבלים. האוטומט מתחיל את הריצה במצב ההתחלה וקורא את אותיות המילה הנתונה בזו אחר זו על פי הסדר. הוא עובר ממצב למצב לאחר קריאת כל אות. בכל שלב, המצב הבא נקבע על ידי המצב הנוכחי של האוטומט והאות הנקראת, על פי חוקי המעבר. הריצה מסתיימת לאחר שהאוטומט גמר לקרוא את כל האותיות במילה. אם בסוף הריצה, האוטומט הגיע לאחד מהמצבים המקבלים, המילה מתקבלת; אחרת, היא נדחית. אוסף המלים שהאוטומט מקבל, (בסימנים, ) נקרא "שפה רגולרית".
את המושג "שפה רגולרית" אפשר להגדיר בדרכים שונות:
לעומת זאת, השפה אינה רגולרית, מאחר שזיהוי מילים בשפה תדרוש מהאוטומט "לספור" מספר לא חסום של אותיות - משימה שאינה אפשרית עבור אוטומט סופי, שזכרונו מוגבל.
אם ו- שפות רגולריות, אז האיחוד שלהן (השפה הכוללת את כל המלים שהן חוקיות באחת משתיהן) גם הוא שפה רגולרית. גם השרשור (השפה בעלת המלים , לכל ו- ) הוא שפה רגולרית. אם שפה רגולרית, גם השפה הנוצרת על-ידה (שהיא השפה שהמלים שלה מורכבות מקטעים ) היא שפה רגולרית.
הווה אומר, אוסף השפות הרגולריות סגור תחת פעולות האיחוד, השרשור, והיצירה. משפט Kleene (פורסם ב-1956) קובע שכל שפה רגולרית אפשר לקבל מן השפות הסינגלטוניות (שפות הכוללות מילה יחידה באורך 1), על ידי שלוש פעולות אלה. הוכחת המשפט היא קונסטרוקטיבית: ידוע אלגוריתם לבניית אוטומט המתאר שפה על-פי המבנה שלה כאיחוד, שרשור ויצירה מתוך שפות סינגלטוניות, ובכיוון ההפוך, יש אלגוריתם שיכול לתאר את השפה שאוטומט נתון מקבל, כאיחוד, שרשור ויצירה של שפות סינגלטוניות.
בכל אוטומט אפשר להפוך את המצבים המקבלים ללא מקבלים ולהפך, וכך להחליף את השפה שהוא מקבל, בשפה המשלימה (הכוללת את כל המלים שנדחו קודם לכן). מכאן יוצא שאוסף השפות הרגולריות סגור, בנוסף לפעולות שהוזכרו לעיל, גם תחת הפעולות של לקיחת משלים, חיתוך והפרש.
ידוע שלכל שפה רגולרית קיים אוטומט יחיד (עד כדי החלפת שמות המצבים), בעל מספר מצבים מינימלי, המתאר אותה.
משפט חשוב אחר, של Schulzenberger (מ-1965) מתאר את משפחת השפות המתקבלות מן השפות הסינגלטוניות על ידי פעולות האיחוד, השרשור והמשלים: אלו הן כולן שפות רגולריות, המתאפיינות בכך שבאוטומט המינימלי המתאר אותן אין מעגלים (למעט, אולי, לולאות באורך 1). פירושו של דבר הוא שהחבורה למחצה הצמודה לאוטומט מקיימת את הזהות , כאשר n הוא מספר המצבים.
משפט זה מספק גם קשר ללוגיקה מתמטית: השפות המתקבלות מפעולות איחוד, שרשור ומשלים, הן השפות הרגולריות שאפשר לתאר באופן פורמלי במסגרת שפה מסדר ראשון. את כל השפות הרגולריות אפשר לתאר במסגרת שפה מסדר שני. קיומה של שפה כדוגמת , שהיא רגולרית אבל אינה ניתנת לבניה בעזרת איחוד, שרשור ופעולת המשלים, מוכיח שהיכולת התאורית של שפות מסדר שני חזקה מזו של כל השפות מסדר ראשון.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.