Абетка (інформатика)

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

Дана абетка $\Sigma$, ми пишемо $\Sigma ^{*}$ щоб позначити набір всіх скінченних рядків над цією абеткою. Тут, ${}^{*}$ позначає оператор зірка Кліні. Ми пишемо $\Sigma ^{\infty }$ (або іноді, $\Sigma ^{\mathbb {N} }$ або $\Sigma ^{\omega }$) для позначення набору всіх нескінченних послідовностей над абеткою $\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. ISBN 0-201-02988-X.