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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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