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

בשפות פורמליות, אלפבית היא קבוצה לא ריקה של סמלים, הנחשבת בדרך כלל כמייצגת אותיות, תווים, או סְפָּרות^[1] אך ייתכן גם שה"סמלים" הללו יהיו קבוצת פונמות (צליל בודד). אלפבית במובן טכני זה של קבוצה, משמש במגוון רחב של תחומים, וביניהם: לוגיקה, מתמטיקה, מדעי המחשב ובלשנות. לאלפבית יכולה להיות כל עוצמה ("גודל") ובהתאם לתפקידו היא עשויה להיות סופית (למשל, האלפבית הלטיני, עם האותיות "a" עד "z"), יכולה להיות בת מנייה (למשל, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{v_1, v_2, \ldots\}} ), או אפילו לא בת מנייה (למשל, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{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 היא קבוצת האותיות "א" עד "ת".

בהינתן אלפבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} , קבוצת כל המילים באורך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} מעל האלפבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} תסומן על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma^n} . הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\textstyle \bigcup_{i \in \mathbb{N}} \Sigma^i} היא קבוצת כל המילים הסופיות (בכל אורך אפשרי) הנוצרת על ידי פעולת כוכב קלין ומסומנת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma^*} , קבוצה זו מכונה גם הסגוּר קליין של האלפבית $\Sigma$ . הסימון הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma^\omega} מציין את קבוצת כל המילים האינסופיות מעל האלפבית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} , ו- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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. מסת"ב 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 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} we mean a nonempty set of symbols.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

[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 הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} we mean a nonempty set of symbols.

[1]