ביטוי רגולרי

ביטוי רגולרי (Regular expression, או regex) הוא רצף תווים שמגדיר תבנית חיפוש. תווי-מטא הם סימנים מיוחדים שמייצגים משמעות אחרת מתו רגיל. למשל נקודה (.) מייצגת כל תו, וסימן ^ מציין תחילת שורה. ביטויים רגולריים משמשים בעיקר לחיפוש והחלפה בטקסט, בעריכות טקסט (כמו Vim), בשפות תכנות ובכלים כמו grep ו-sed. סט נפוץ של כללים נקרא PCRE (Perl Compatible Regular Expressions).

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

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

קיים יחס שקילות: לכל ביטוי רגולרי יש שפה רגולרית שמתאימה לו, ולהפך. הכיוון הראשון נקבע באינדוקציה: שפות בסיסיות נשארות רגולריות בזמן שאיחוד, שרשור ואיטרציה שומרים על רגולריות. הכיוון ההפוך נעשה על ידי בניית ביטוי רגולרי מתוך אוטומט סופי דטרמיניסטי (מכונה עם מצבים). בהוכחה זו מגדירים שפות עזר L_{ij}^k ואופרטור רקורסיבי שלפיו אפשר לבנות ביטוי לכל זוג מצבים, בעיקר:
r_{ij}^k = r_{ik}^{k-1} (r_{kk}^{k-1})* r_{kj}^{k-1} + r_{ij}^{k-1}
כך מייצרים ביטויים מכל אוטומט סופי.

בוטים, אתרי אינטרנט וקבצי נתונים משתמשים בביטויים רגולריים כדי לזהות תבניות כמו מספרי טלפון. דוגמה לייצוג מספר טלפון רלוונטי בתצורה נפוצה היא 0[0-9][0-9]?-[0-9]{7}. בשפות תכנות רבות התמיכה בביטויים רגולריים מרחיבה את היכולות גם מעבר להגדרה התיאורטית. עם זאת, ברמת הרעיון, ביטויים רגולריים הם כלי חזק ונפוץ לטיפול בטקסט.

ביטוי רגולרי הוא דפוס שמחפש טקסט. דפוס זה עוזר למחשב למצוא מחרוזות.

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

1*0* אומר: כמה 1-ים ואז כמה 0-ים. ab[2-5]de מתאים ל-ab2de עד ab5de. a.b אומר a, ואז כל תו, ואז b. ab*c אומר a, ואז אפשר אפס או יותר b, ואז c.

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