В теоретической информатике правило Ардена , также известное как лемма Ардена , представляет собой математическое утверждение об определенной форме языковых уравнений .
( Формальный ) язык — это просто набор строк. Такие множества можно задать с помощью некоторого уравнения языка , которое, в свою очередь, основано на операциях над языками. Уравнения языка — это математические операторы, которые напоминают числовые уравнения, но переменные принимают значения формальных языков, а не чисел. Среди наиболее распространенных операций над двумя языками A и B являются объединение множеств A ∪ B и их конкатенация A ⋅ B . Наконец, как операция, принимающая один операнд , множество A * обозначает звезду Клини .языка А. _
Правило Ардена гласит, что множество A * ⋅ B является наименьшим языком, который является решением для X в линейном уравнении X = A ⋅ X ∪ B , где X , A , B — наборы строк. Более того, если множество A не содержит пустого слова, то это решение единственно. [1] [2]
Правило Ардена можно использовать для преобразования некоторых конечных автоматов в регулярные выражения, как в алгоритме Клини .