הצגת המקור של הדף "אלפבית (שפה פורמלית)"

[[שפה פורמלית|בשפות פורמליות]], '''אלפבית''' היא [[קבוצה (מתמטיקה)|קבוצה]] לא ריקה של סמלים, הנחשבת בדרך כלל כמייצגת אותיות, תווים, או סְפָּרות<ref name="ebbinghaus">{{Cite book|url=https://www.springer.com/mathematics/book/978-0-387-94258-2|title=Mathematical Logic|last=Ebbinghaus|first=H.-D.|last2=Flum|first2=J.|last3=Thomas|first3=W.|date=1994|publisher=[[Springer Science+Business Media|Springer]]|isbn=0-387-94258-0|edition=2nd|location=[[New York City|New York]]|page=11|quote=By an ''alphabet'' <math>\mathcal{A}</math> we mean a nonempty set of ''symbols''.}}</ref> אך ייתכן גם שה"סמלים" הללו יהיו קבוצת [[פונמה|פונמות]] (צליל בודד). אלפבית במובן טכני זה של קבוצה, משמש במגוון רחב של תחומים, וביניהם: [[לוגיקה]], [[מתמטיקה]], [[מדעי המחשב]] ובלשנות. לאלפבית יכולה להיות כל [[עוצמה (מתמטיקה)|עוצמה]] ("גודל") ובהתאם לתפקידו היא עשויה להיות [[קבוצה סופית|סופית]] (למשל, האלפבית הלטיני, עם האותיות "a" עד "z"), יכולה להיות [[קבוצה בת מנייה|בת מנייה]] (למשל, <math>\{v_1, v_2, \ldots\}</math>), או אפילו [[קבוצה שאינה בת מנייה|לא בת מנייה]] (למשל, <math>\{v_x : x \in \mathbb{R} \}</math>).

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

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

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

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

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

בהינתן אלפבית <math>\Sigma</math>, קבוצת כל המילים באורך <math>n</math> מעל האלפבית <math>\Sigma</math> תסומן על ידי <math>\Sigma^n</math> . הקבוצה <math display="inline">\bigcup_{i \in \mathbb{N}} \Sigma^i</math> היא קבוצת כל המילים הסופיות (בכל אורך אפשרי) הנוצרת על ידי פעולת [[כוכב קלין]] ומסומנת <math>\Sigma^*</math>, קבוצה זו מכונה גם הסגוּר קליין של האלפבית <math>\Sigma</math> . הסימון <math>\Sigma^\omega</math> מציין את קבוצת כל המילים האינסופיות מעל האלפבית <math>\Sigma</math>, ו- <math>\Sigma^\infty</math> מציין את הקבוצה <math>\Sigma^\ast \cup \Sigma^\omega</math> כלומר את כל המילים הסופיות או האינסופיות.

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

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

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

== ראו גם ==
* קומבינטוריקה על מילים

== לקריאה נוספת ==
<div class="mw-content-ltr">
* 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 (identifier)|ISBN]] [[Special:BookSources/0-201-02988-X|0-201-02988-X]].
</div>

==הערות שוליים==
{{הערות שוליים}}
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:שפות פורמליות]]