В інформатиці і математичній логіці, абетка це скінченний набір символів або літер, наприклад букви і цифри. Найбільш вживана абетка це {0,1}, двійкова абетка. Скінченний рядок це скінченна послідовність літер з абетки; наприклад двійковий рядок це рядок утворений з абетки {0,1}. Нескінченні послідовності літер так само можуть бути утворені з елементів будь-якої абетки.
Дана абетка , ми пишемо щоб позначити набір всіх скінченних рядків над цією абеткою. Тут, позначає оператор зірка Кліні. Ми пишемо (або іноді, або ) для позначення набору всіх нескінченних послідовностей над абеткою .
Наприклад, якщо ми використовуємо двійкову абетку {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.