Ardensovo pravidlo - Ardens rule - Wikipedia

v teoretická informatika, Ardenovo pravidlo, také známý jako Ardenovo lemma, je matematický výrok o určité formě jazykové rovnice.

Pozadí

A (formální jazyk je prostě sada řetězců. Takové sady lze určit pomocí některých jazyková rovnice, což je zase založeno na operacích v jazycích. Jazykové rovnice jsou matematické výroky, které se podobají numerickým rovnicím, ale proměnné předpokládají spíše hodnoty formálních jazyků než čísel. Mezi nejběžnější operace ve dvou jazycích A a B jsou nastavit unii A ∪ B, a jejich zřetězení A⋅B. A konečně, jako operace s jediným operand, sada A* označuje Kleene hvězda jazyka A.

Prohlášení o Ardenově pravidle

Ardenovo pravidlo říká, že množina A*⋅B je nejmenší jazyk, pro který je řešení X v lineární rovnice X = A⋅X ∪ B kde X, A, B jsou sady řetězců. Navíc, pokud je sada A neobsahuje prázdné slovo, pak je toto řešení jedinečné.[1][2]

Ekvivalentně, sada B⋅A* je nejmenší jazyk, pro který je řešení X v X = X⋅A ∪ B.

aplikace

Ardenovo pravidlo lze použít k převodu některých konečných automatů na regulární výrazy, jako v Kleenův algoritmus.

Viz také

Poznámky

  1. ^ Daintith, John (2004). „Ardenovo pravidlo“. Archivováno z původního dne 13. února 2010. Citováno 10. března 2010.
  2. ^ Sutner, Klaus. „Algebra běžných jazyků“ (PDF). Archivovány od originál (PDF) dne 8.7.2011. Citováno 15. února 2011.

Reference

  • Arden, D. N. (1960). Stroje se zpožděnou logikou a konečným stavem, Teorie konstrukce výpočetních strojů, s. 1-35, University of Michigan Press, Ann Arbor, Michigan, USA.
  • Dean N.Arden (říjen 1961). „Zpožděné logické a konečné stavové automaty“. Proc. 2. Ann. Symp. o teorii spínacích obvodů a logickém designu (SWCT), Detroit / MI. (abstrakt s otevřeným přístupem)
  • John E. Hopcroft a Jeffrey D. Ullman, Úvod do teorie automatů, jazyků a výpočtu, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN  0-201-02988-X. Kapitola 2: Konečné automaty a regulární výrazy, str.54.