ביטוי רגולרי
ביטוי רגולרי הוא דפוס שמחפש טקסט. דפוס זה עוזר למחשב למצוא מחרוזות. בונים ביטוי מתוך אותיות ופעולות פשוטות. הפעולות החשובות הן: חיבור (או), שרשור (אחד אחרי השני) וכוכב קלין (חזרה כמה פעמים). 1*0* אומר: כמה 1-ים ואז כמה 0-ים. ab[2-5]de מתאים ל-ab2de עד ab5de. a.b אומר a, ואז כל תו, ואז b. ab*c אומר...
שפה רגולרית
שפה רגולרית היא קבוצת מילים שאפשר לבדוק בעזרת מכונה פשוטה. מכונה פשוטה יש לה מצבים (תיבות), מצב התחלה, ומצבים שמקבלים. המכונה קוראת אותיות אחת אחת ועוברת בין התיבות לפי חוקים. אם בסוף היא בעמדת קבלה, המילה טובה. המכונה מתחילה בתיבה מיוחדת. היא קוראת את המילה מהתחלה לסוף. כל אות גורמת לה להחליף תיב...