Регулярна подія

Матеріал з Вікіпедії — вільної енциклопедії.

Регулярна подія — множина слів деякого алфавіту, отримана із однолітерних слів із допомогою скінченої кількості застосувань наступних операцій до множини слів:

  • теоретико-множинне об'єднання AB;
  • добуток A·B, який визначається як множина слів, які мають вигляд αβ (α ∈ A, β ∈ B);
  • ітерація {A}, яка визначається як {A} = AA · AA · A · AA · A × A · A ∪ ... (існує і інше визначення ітерації, коли вимагають, щоб до {A} належало порожнє слово e, тобто, вважають {A} = eAA · AA · A · AA · A · A · A · A ∪ ...).

Так як справедлива теорема, в якій стверджується, що регулярні події, і тільки вони представимі в скінчених автоматах, поняття регулярних подій є одним із основних в алгебраїчній теорії автоматів.

[ред.] Джерела інформації

[ред.] Дивіться також


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.