Правило Арденса - Ardens rule - Wikipedia

В теоретическая информатика, Правило Ардена, также известный как Лемма Ардена, является математическим утверждением об определенной форме языковые уравнения.

Фон

А (формальный язык это просто набор строк. Такие наборы могут быть указаны с помощью некоторых языковое уравнение, который, в свою очередь, основан на операциях с языками. Уравнения языка - это математические утверждения, которые напоминают числовые уравнения, но переменные принимают значения формальных языков, а не числа. Среди наиболее распространенных операций на двух языках А и B являются установить союз А ∪ B, и их конкатенация А⋅B. Наконец, как операция, требующая одного операнд, набор А* обозначает Клини звезда языка А.

Заявление о правилах Ардена

Правило Ардена гласит, что набор А*⋅B наименьший язык, который является решением для Икс в линейное уравнение Икс = А⋅Икс ∪ B куда Икс, А, B представляют собой наборы строк. Более того, если множество А не содержит пустого слова, то это решение единственное.[1][2]

Эквивалентно набор B⋅А* наименьший язык, который является решением для Икс в Икс = Икс⋅А ∪ B.

Заявление

Правило Ардена можно использовать для преобразования некоторых конечных автоматов в регулярные выражения, как в Алгоритм Клини.

Смотрите также

Примечания

  1. ^ Дейнтит, Джон (2004). «Правило Ардена». В архиве из оригинала 13 февраля 2010 г.. Получено 10 марта 2010.
  2. ^ Сатнер, Клаус. «Алгебра регулярных языков» (PDF). Архивировано из оригинал (PDF) на 2011-07-08. Получено 15 февраля 2011.

Рекомендации

  • Арден, Д. Н. (1960). Логика с задержкой и конечные автоматы, Теория проектирования вычислительных машин, pp. 1-35, University of Michigan Press, Ann Arbor, Michigan, USA.
  • Дин Н. Арден (октябрь 1961 г.). «Логика с запаздыванием и конечные автоматы». Proc. 2nd Ann. Symp. по теории коммутационных цепей и логическому проектированию (SWCT), Детройт / Мичиган. (аннотация в открытом доступе)
  • Джон Э. Хопкрофт и Джеффри Д. Уллман, Введение в теорию автоматов, языки и вычисления, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN  0-201-02988-X. Глава 2: Конечные автоматы и регулярные выражения, стр. 54.