Алфавіт (математика)

В інформатиці і математичній логіці, абетка це скінченний набір символів або літер, наприклад букви і цифри. Найбільш вживана абетка це {0,1}, двійкова абетка. Скінченний рядок це скінченна послідовність літер з абетки; наприклад двійковий рядок це рядок утворений з абетки {0,1}. Нескінченні послідовності літер так само можуть бути утворені з елементів будь-якої абетки.

Дана абетка ${\displaystyle \Sigma }$, ми пишемо ${\displaystyle \Sigma ^{*}}$ щоб позначити набір всіх скінченних рядків над цією абеткою. Тут, ${\displaystyle {}^{*}}$ позначає оператор зірка Кліні. Ми пишемо ${\displaystyle \Sigma ^{\infty }}$ (або іноді, ${\displaystyle \Sigma ^{\mathbb {N} }}$ або ${\displaystyle \Sigma ^{\omega }}$) для позначення набору всіх нескінченних послідовностей над абеткою ${\displaystyle \Sigma }$.

Наприклад, якщо ми використовуємо двійкову абетку {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. .