שפה רגולרית
שפה רגולרית היא קבוצת מילים שאפשר לבדוק בעזרת מכונה פשוטה. מכונה פשוטה יש לה מצבים (תיבות), מצב התחלה, ומצבים שמקבלים. המכונה קוראת אותיות אחת אחת ועוברת בין התיבות לפי חוקים. אם בסוף היא בעמדת קבלה, המילה טובה. המכונה מתחילה בתיבה מיוחדת. היא קוראת את המילה מהתחלה לסוף. כל אות גורמת לה להחליף תיב...
למת הניפוח לשפות רגולריות
למת הניפוח היא דרך לבדוק אם שפה מתנהגת כמו מחשב קטן. היא הוצעה על ידי בר-הלל, פרלס ושמיר. אם מכונה קטנה יכולה לזהות שפה, אז במילים ארוכות יש קטע שחוזר. אפשר להוציא את הקטע הזה או לחזור עליו, והמילה תישאר בשפה. אם השפה רגולרית, יש מספר n כזה: כל מילה ארוכה מ-n מתחלקת ל-u, v, w כך ש- 1. החלק u ו-v...
אוטומט סופי
מתג של נורה הוא דוגמה פשוטה לאוטומט סופי. אוטומט סופי הוא מכונה פשוטה עם מספר מצבים קטן. היא קוראת אותיות במילה ומחליטה אם לקבל אותה. אוטומט דטרמיניסטי תמיד יודע מצב יחיד להמשיך אליו אחרי קריאת אות. זה כמו דרך ברורה ללכת בה. אוטומט לא־דטרמיניסטי יכול לבחור בין כמה דרכים. הוא גם יכול לעבור מקום ב...
משפט מייהיל-נרוד
משפט מייהיל-נרוד מסביר איך להבין שפות רגולריות בעזרת חלוקה של מילים לקבוצות. השם מגיע מאניל נרוד וג'ון מייהיל. נגדיר יחס שקילות. יחס שקילות הוא דרך לחלק מילים לקבוצות לפי התנהגותן. שתי מילים x ו-y שייכות לאותה קבוצה אם לכל מילה z, ההוספה של z אל x ואל y מחזירה תוצאה שתקבע אם הן בשפה או לא. מילה שמפ...