Reguła Ardena

W informatyce teoretycznej reguła Ardena , znana również jako lemat Ardena , jest matematycznym stwierdzeniem dotyczącym pewnej formy równań językowych .

Tło

Język (formalny) to po prostu zestaw ciągów znaków. Takie zbiory można określić za pomocą pewnego równania językowego , które z kolei opiera się na operacjach na językach. Równania językowe to wyrażenia matematyczne, które przypominają równania numeryczne, ale zmienne przyjmują wartości języków formalnych, a nie liczb. Wśród najczęstszych operacji na dwóch językach A i B jest suma zbiorów A ∪ B , oraz ich konkatenacja A ⋅ B . Wreszcie, jako operacja na pojedynczym argumencie , zbiór A ^* oznacza gwiazdę Kleene'a języka A .

Oświadczenie o rządzie Ardena

Reguła Ardena mówi, że zbiór A ^* ⋅ B jest najmniejszym językiem, który jest rozwiązaniem dla X w równaniu liniowym X = A ⋅ X ∪ B , gdzie X , A , B to zbiory ciągów znaków. Co więcej, jeśli zbiór A nie zawiera słowa pustego, to rozwiązanie to jest unikalne.

Równoważnie, zbiór B ⋅ A ^* jest najmniejszym językiem, który jest rozwiązaniem dla X w X = X ⋅ A ∪ B .

Aplikacja

Reguła Ardena może być wykorzystana do konwersji niektórych automatów skończonych na wyrażenia regularne, jak w algorytmie Kleene'a .

Zobacz też

Notatki

Arden, DN (1960). Logika opóźniona i maszyny skończone, Theory of Computing Machine Design , s. 1-35, University of Michigan Press, Ann Arbor, Michigan, USA.
Dean N. Arden (październik 1961). „Logika opóźniona i automaty skończone” . proc. 2 Ann. Symp. w sprawie teorii obwodów przełączających i projektowania logicznego (SWCT), Detroit/MI . (abstrakt w otwartym dostępie)
John E. Hopcroft i Jeffrey D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . Rozdział 2: Automaty skończone i wyrażenia regularne, s. 54.
Arden, DN Wprowadzenie do teorii skończonych maszyn stanowych , monografia nr 12, projekt koncepcji systemu dyskretnego, 28 czerwca 1965 r.