בתורת השפות הפורמליות, שפה רגולרית היא שפה פורמלית שאפשר לתאר על ידי אוטומט סופי, האמור לקבוע לגבי מילה נתונה אם היא שייכת לשפה אם לאו. משפחת השפות הרגולריות היא המשפחה הראשונה בהיררכיית השפות של חומסקי.
הגדרה.
אוטומט סופי דטרמיניסטי הוא מערכת הכוללת מספר סופי של מצבים וחוקי מעבר ממצב למצב, התלויים בקלט. אחד המצבים מוגדר כמצב ההתחלה. חלק מהמצבים מוגדרים כמצבים מקבלים. האוטומט מתחיל את הריצה במצב ההתחלה וקורא את אותיות המילה הנתונה בזו אחר זו על פי הסדר. הוא עובר ממצב למצב לאחר קריאת כל אות. בכל שלב, המצב הבא נקבע על ידי המצב הנוכחי של האוטומט והאות הנקראת, על פי חוקי המעבר. הריצה מסתיימת לאחר שהאוטומט גמר לקרוא את כל האותיות במילה. אם בסוף הריצה, האוטומט הגיע לאחד מהמצבים המקבלים, המילה מתקבלת; אחרת, היא נדחית. אוסף המלים שהאוטומט formula_1 מקבל, (בסימנים, formula_2) נקרא "שפה רגולרית".
את המושג "שפה רגולרית" אפשר להגדיר בדרכים שונות:
דוגמאות.
לעומת זאת, השפה formula_5 אינה רגולרית, מאחר שזיהוי מילים בשפה תדרוש מהאוטומט "לספור" מספר לא חסום של אותיות - משימה שאינה אפשרית עבור אוטומט סופי, שזכרונו מוגבל.
תכונות מרכזיות של שפות רגולריות.
אם formula_6 ו- formula_7 שפות רגולריות, אז האיחוד שלהן (השפה הכוללת את כל המלים שהן חוקיות באחת משתיהן) גם הוא שפה רגולרית. גם השרשור (השפה בעלת המלים formula_8, לכל formula_9 ו- formula_10) הוא שפה רגולרית. אם formula_11 שפה רגולרית, גם השפה הנוצרת על-ידה (שהיא השפה formula_12 שהמלים שלה formula_13 מורכבות מקטעים formula_14) היא שפה רגולרית.
הווה אומר, אוסף השפות הרגולריות סגור תחת פעולות האיחוד, השרשור, והיצירה. משפט Kleene (פורסם ב-1956) קובע שכל שפה רגולרית אפשר לקבל מן השפות הסינגלטוניות (שפות הכוללות מילה יחידה באורך 1), על ידי שלוש פעולות אלה. הוכחת המשפט היא קונסטרוקטיבית: ידוע אלגוריתם לבניית אוטומט המתאר שפה על-פי המבנה שלה כאיחוד, שרשור ויצירה מתוך שפות סינגלטוניות, ובכיוון ההפוך, יש אלגוריתם שיכול לתאר את השפה שאוטומט נתון מקבל, כאיחוד, שרשור ויצירה של שפות סינגלטוניות.
בכל אוטומט אפשר להפוך את המצבים המקבלים ללא מקבלים ולהפך, וכך להחליף את השפה שהוא מקבל, בשפה המשלימה (הכוללת את כל המלים שנדחו קודם לכן). מכאן יוצא שאוסף השפות הרגולריות סגור, בנוסף לפעולות שהוזכרו לעיל, גם תחת הפעולות של לקיחת משלים, חיתוך והפרש.
ידוע שלכל שפה רגולרית קיים אוטומט יחיד (עד כדי החלפת שמות המצבים), בעל מספר מצבים מינימלי, המתאר אותה.
משפט חשוב אחר, של Schulzenberger (מ-1965) מתאר את משפחת השפות המתקבלות מן השפות הסינגלטוניות על ידי פעולות האיחוד, השרשור והמשלים: אלו הן כולן שפות רגולריות, המתאפיינות בכך שבאוטומט המינימלי המתאר אותן אין מעגלים (למעט, אולי, לולאות באורך 1). פירושו של דבר הוא שהחבורה למחצה הצמודה לאוטומט מקיימת את הזהות formula_15, כאשר n הוא מספר המצבים.
משפט זה מספק גם קשר ללוגיקה מתמטית: השפות המתקבלות מפעולות איחוד, שרשור ומשלים, הן השפות הרגולריות שאפשר לתאר באופן פורמלי במסגרת שפה מסדר ראשון. את כל השפות הרגולריות אפשר לתאר במסגרת שפה מסדר שני. קיומה של שפה כדוגמת formula_16, שהיא רגולרית אבל אינה ניתנת לבניה בעזרת איחוד, שרשור ופעולת המשלים, מוכיח שהיכולת התאורית של שפות מסדר שני חזקה מזו של כל השפות מסדר ראשון.
ארכון
ארכון (מיוונית: Αρχων, שפירושו: "שליט"; ברבים Ρχοντες) היה נושא משרה בכירה בכמה פוליס (ערי מדינה) ביוון העתיקה ובמיוחד באתונה העתיקה.
ארכונטים באתונה.
תפקיד הארכונטים נוצר כתוצאה מהפלת המלוכה באתונה והצורך להחליף את המלך בתפקידיו השונים. במקורן היו משרות הארכונטים מאוישות על ידי בני האצולה האתונאית (האֵוּפַּטְרִים). למשך עשר שנים, אולם בשנת 683 לפנה"ס קוצרה תקופת כהונתם של הארכונטים לשנה.
כאשר פייסיסטראטוס יסד את הטיראניה באתונה בשנת 561 לפנה"ס, הוא בחר ארכונטים מאנשי שלומו ובכך רוקן את מוסד הארכונטים מתוכן, מכיוון שהוא היה זה שקיבל את ההחלטות בפועל.
בשנת 487 לפנה"ס אוישו משרות הארכונטים על ידי הטלת פור בין כל אזרחי אתונה, ובשנת 457 לפנה"ס נפתחה המשרה גם לאזרחים ממעמד הזאוגיטים.
התסמותטים היו שישה נושאי משרות שכמו הארכונטים כיהנו למשך שנה. תפקידם היה לטפל בפניות המשפטיות אל הארכונטים והם היו ממונים על לוח הזמנים של המשפטים ועל שיבוץ הארכונטים השונים לשפיטה. בשלב מסוים נוסף אל התסמותטים מזכיר.
בתום כהונתם של הארכונטים והתסמותטים הם הצטרפו למועצת האריאופגוס.
ארכון בסילאי.
הארכון הבסילאי (Βασιλεύς, "מלך") מילא בעיקר תפקידים דתיים בחיי הפוליס אתונה שבמקור מילא מלך אתונה. הוא היה מופקד על ניהול פולחני אלים אחדים, והוא היה השופט במקרים של האשמות בחילול הקודש או מחלוקות דתיות אחרות, הייתה לו גם סמכות שיפוט משפטית, והוא היה אחראי על הפניית מקרים משפטיים של רצח, פציעה והריגה אל בתי המשפט והוא כנראה כיהן כיושב ראש השופטים במשפטים האלה.
ארכון פולמרכי.
הארכון הפולמרכי (או פשוט פולמרכוס) נטל לידיו בתחילה את התפקיד הצבאי של מלך אתונה כמפקד הצבא, אולם עם הזמן הוא איבד מסמכויותיו ואלו עברו אל הסטרטגים, אבל הוא עדיין שמר על סמכות הפיקוד העליונה וכמו כן הוא היה האחראי על קיום הטקסים הדתיים לאלי המלחמה וכמו כן הייתה לו סמכות להפנות מקרים משפטיים שהיו מעורבים בהם זרים ומטויקים לבתי המשפט המתאימים.
ארכון אפונימי.
משרת הארכון האפונימי נחשבה ליוקרתית ביותר באתונה מכיוון שעל שם נושא המשרה נקראה השנה, הוא היה מופקד על ביצועם התקין של הליטורגיות, הוא היה מארגן התהלוכות לכבוד האלים דיוניסוס ואסקלפיוס, כמו כן היו סמכויות שיפוט במקרים משפטיים שנגעו לדיני משפחה והוא היה מופקד על הגנת האלמנות והיתומים.
ארכונטים מחוץ לאתונה.
עם התחזקות מעמדה של אתונה בתוך הברית האטית-דלית, והפיכת הברית למכשיר שליטה אימפריאליסטית של אתונה, אתונה נהגה לכפות על בנות בריתה בברית משטר הדמוקרטי הדומה לשלה וככה נוצרו משמרות ארכונטים בפולייס שהיו חברות בברית.
למת הניפוח לשפות רגולריות
למת הניפוח נועדה להוכיח ששפה formula_1 כלשהי איננה שפה רגולרית. הלמה מגדירה תנאי הכרחי לרגולריות שפה, והשימוש העיקרי בה הוא בהוכחה בדרך השלילה ששפה איננה רגולרית על ידי הוכחת אי קיומו של התנאי עליו מדברת הלמה. הלמה נוסחה והוכחה על ידי יהושע בר-הלל, מיכה פרלס, ואלי שמיר מהאוניברסיטה העברית בירושלים.
הרעיון האינטואיטיבי של למת הניפוח.
שפה רגולרית היא שפה שקיים אוטומט סופי דטרמיניסטי שמקבל אותה. כלומר, שפה שדי בכמות סופית ומוגבלת של זיכרון כדי להחליט אם מילה שייכת אליה או לא. לכן, טבעי לצפות כי במילים גדולות מספיק תהיה תבנית חוזרת כלשהי, שמספר ההופעות שלה אינו משפיע על שייכות המילה לשפה. זאת מכיוון שמילה שאין בה שום תבנית חוזרת דורשת כמות זיכרון השווה לאורכה כדי לעקוב אחרי כל האותיות בה, מה שהופך קבלת מילים שגודלן עולה על הזיכרון העומד לרשות האוטומט לבלתי אפשרי.
לכן, אם מילה בשפה רגולרית היא גדולה מספיק, ניתן לפרק אותה לשלושה חלקים: התחלה, אמצע וסוף (ההתחלה והסוף יכולים להיות גם ריקים) כאשר חלק ה"אמצע" הוא החלק של התבנית שחוזר על עצמו. לאחר שהתבצעה חלוקה זו ניתן להוריד את קטע ה"אמצע", או לשכפל אותו מספר כלשהו של פעמים (ומכאן המילה "ניפוח" שבשם הלמה, שכן כך אנו "מנפחים" את המילה) ועדיין לקבל מילה השייכת לשפה הרגולרית.
ייתכן שגם שפות שאינן רגולריות יכילו בתוכן תבנית כלשהי, ולכן ייתכן שלמת הניפוח תתקיים גם עבור שפות שאינן רגולריות. אולם על פי הלמה כל שפה שהיא רגולרית ניתנת לניפוח, ולכן אם לא ניתן לנפח שפה כלשהי, הדבר גורר את היותה אי-רגולרית.
למת הניפוח לשפות הרגולריות.
תהי formula_1 שפה רגולרית. אז קיים מספר טבעי formula_3, כך שכל מילה formula_4 ב-formula_1, שאורכה לפחות formula_3, ניתנת לפירוק מהצורה formula_7, באופן שמתקיימים התנאים האלה:
1. formula_8
2. formula_9
3. לכל formula_10 טבעי מתקיים formula_11
כמובן, ייתכן מצב בו formula_12 או formula_13.
התנאי הראשון מספק חסם על אורך הקטע הניתן לניפוח ומרחקו מתחילת המילה, מה שלעיתים עוזר להראות בצורה יעילה יותר שניפוח איננו אפשרי.
התנאי השני מבטיח לנו שהקטע שאותו אנו מנפחים אינו טריוויאלי (כלומר, יש בו לפחות אות אחת).
התנאי השלישי מתאר את הניפוח עצמו: עבור כל מספר שכפולים (כולל 0) של קטע הניפוח, מקבלים מילה השייכת לשפה.
דוגמאות.
שפה שאינה ניתנת לניפוח.
השפה formula_14 ידועה כשפה לא רגולרית. נראה כיצד ניתן להשתמש בלמת הניפוח כדי לראות זאת.
נניח בשלילה כי השפה כן רגולרית, אז קיים ה- formula_3 שקיומו מובטח על ידי המשפט. נביט במילה formula_16. אורכה גדול מ-formula_3 (הוא בדיוק formula_18) ולכן המילה ניתנת לניפוח, כלומר קיים לה פירוק formula_19 כמתואר.
כעת, מכיוון ש-formula_20 בהכרח formula_21, שכן formula_3 האותיות הראשונות במילה הן formula_23-ים. לכן formula_24 כאשר formula_25 (שהרי מהלמה formula_9).
כעת נביט על המילה formula_27, כלומר formula_28. מילה זו שייכת לשפה על פי למת הניפוח. אבל היא בדיוק מהצורה formula_29 ומכיוון ש-formula_30 הרי שבהכרח formula_31, והגענו לסתירה, כי כל המילים בשפה הן כאלו שבהן מספר ה-formula_23-ים וה-formula_33-ים זהה. לכן formula_34 אינה שפה רגולרית.
שפה רגולרית שאינה ניתנת לניפוח.