אלפבית (שפה פורמלית)

בשפות פורמליות, אלפבית היא קבוצה לא ריקה של סמלים, הנחשבת בדרך כלל כמייצגת אותיות, תווים, או סְפָּרות^[1] אך ייתכן גם שה"סמלים" הללו יהיו קבוצת פונמות (צליל בודד). אלפבית במובן טכני זה של קבוצה, משמש במגוון רחב של תחומים, וביניהם: לוגיקה, מתמטיקה, מדעי המחשב ובלשנות. לאלפבית יכולה להיות כל עוצמה ("גודל") ובהתאם לתפקידו היא עשויה להיות סופית (למשל, האלפבית הלטיני, עם האותיות "a" עד "z"), יכולה להיות בת מנייה (למשל, $\{v_{1},v_{2},\ldots \}$ ), או אפילו לא בת מנייה (למשל, $\{v_{x}:x\in \mathbb {R} \}$ ).

מחרוזות, המכונות גם "מילים", מעל אלפבית מוגדרות כרצף של סמלים מתוך קבוצה זו. לדוגמה, אלפבית האותיות הקטנות "a" עד "z" יכול לשמש ליצירת מילים באנגלית כמו "iceberg" ואילו האלפבית של האותיות הקטנות והגדולות יכול לשמש גם ליצירת שמות נכונים דקדוקית כמו "Wikipedia". אלפבית נפוץ הוא {0,1}, האלפבית הבינארי, ו-"00101111" היא דוגמה למילה מעליו, כלומר מחרוזת בינארית. ניתן להביט גם על מילים אינסופיות מעל אלפבית זה.

לעיתים קרובות עבור מטרות מעשיות ניאלץ להגביל את סוג הסמלים באלפבית כך שהם יהיו חד-משמעיים כאשר נקרא אותם. למשל, אם באלפבית שלנו ישנם שני האיברים {00,0}, מחרוזת הכתובה על נייר כ- "000" איננה חד משמעית מכיוון שלא ברור האם זה רצף של שלושה סמלי "0", או הסימן "00" ואחריו "0", או שמא מדובר ב-"0" ואחריו "00".

סימונים

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

לדוגמה, אם L היא קבוצת כל מזהי המשתנים בשפת התכנות C, האלפבית של L היא הקבוצה {a, b, c, ..., x, y, z, A, B, C,. . ., X, Y, Z, 0, 1, 2, ..., 7, 8, 9, _}.

ואם L היא קבוצת כל המילים בשפה העברית, האלפבית של L היא קבוצת האותיות "א" עד "ת".

בהינתן אלפבית $\Sigma$ , קבוצת כל המילים באורך $n$ מעל האלפבית $\Sigma$ תסומן על ידי $\Sigma ^{n}$ . הקבוצה ${\textstyle \bigcup _{i\in \mathbb {N} }\Sigma ^{i}}$ היא קבוצת כל המילים הסופיות (בכל אורך אפשרי) הנוצרת על ידי פעולת כוכב קלין ומסומנת $\Sigma ^{*}$ , קבוצה זו מכונה גם הסגוּר קליין של האלפבית $\Sigma$ . הסימון $\Sigma ^{\omega }$ מציין את קבוצת כל המילים האינסופיות מעל האלפבית $\Sigma$ , ו- $\Sigma ^{\infty }$ מציין את הקבוצה $\Sigma ^{\ast }\cup \Sigma ^{\omega }$ כלומר את כל המילים הסופיות או האינסופיות.

לדוגמה, מעל האלפבית הבינארי {0,1}, המילים ε, 0, 1, 00, 01, 10, 11, 000 וכו' נמצאות כולן בסגור קליין של האלפבית (כאשר ε מייצג את המילה הריקה ).

יישומים

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

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

ראו גם

קומבינטוריקה על מילים

לקריאה נוספת

John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X ISBN 0-201-02988-X.

הערות שוליים

^ Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (2nd ed.). New York: Springer. p. 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols.

[ebbinghaus-1] Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994). Mathematical Logic (2nd ed.). New York: Springer. p. 11. ISBN 0-387-94258-0. By an alphabet ${\mathcal {A}}$ we mean a nonempty set of symbols.

[1]