Abstraktní rodina jazyků

V teoretické informatice , a zejména v teorii formálních jazyků , pojem rodina abstraktních jazyků odkazuje na koncept, který zobecňuje společné charakteristiky racionálního jazyka , algebraických jazyků , na rekurzivně spočetné jazyky a mnoho dalších rodin formálních jazyků.

Definice

Formální jazyk je soubor slov na konečných abecedy , to znamená, je součástí volného monoid , kde * označuje Kleenova hvězdu . $L$ $NA$ $A ^ {*}$

Rodina jazyků je dvojice tvořena z nekonečného abecedy označeny a pro nějakou konečnou část města , z řady formálních jazyků na . $\ Sigma$ $NA$ $\ Sigma$ $NA$

Racionální kužel (nazvaný plný trio v angličtině) je řada uzavřených jazyků operací morfismu, inverzní morfismu a křižovatkou s racionálními jazyky.
Věrný racionální kužel (nazvaný trio v angličtině) je řada uzavřených jazyků provozu non-Vymazání morfismu, inverzní morfismu a křižovatkou s racionálními jazyky.

Jazyková rodina je racionálně uzavřena, pokud je uzavřena pro operace sjednocení, produktu a Kleene .
Abstraktní rodina jazyků ( plná abstraktní rodina jazyků nebo plné AFL v angličtině) je racionální kužel, který je navíc racionálně uzavřen.

Abstraktní rodina věrnými jazyky ( abstraktní rodina jazyků nebo AFL v angličtině) je racionálně uzavřen věrný racionální kužel.

Také se setkáváme s představou semi-AFL pro racionální kužel uzavřený sjednocením.

Příklady abstraktních rodin jazyků a vlastností

Tyto jazyky racionální tvoří abstraktní rodina jazyků.

Tyto algebraické jazyky tvoří rodinnou abstraktních jazyků.

Tyto kontextové jazyky tvoří abstraktní rodinné věrnými jazyky, protože nejsou uzavřeny jakýmkoliv morfismu.

Tyto rekurzivně spočetný jazyk tvoří abstraktní rodinu věrných jazyků stejně jako rekurzivní jazyky .

Každý racionální kužel obsahuje rodinu racionálních jazyků.

Tyto lineární jazyky tvořit racionální kužel uzavřený unie. Podobně kvazi-racionální jazyky tvoří racionální kužel uzavřený unií. Lineární jazyky nejsou racionálně uzavřené, kvazi-racionální jazyky ano.

Ostatní operace nejsou vyjádřeny pomocí racionálních transdukčních operací nebo uzavřením pro racionální operace. Jedná se zejména o zamíchání , zrcadlový obraz, substituce.

Původ

První referát zabývající se abstraktními rodinami jazyků představili Seymour Ginsburg a Sheila Greibach na osmém sympoziu série Symposium on Switching and Automata Theory v roce 1967.

Poznámky

(en) Ginsburg a Greibach (1967) .

Reference

(en) Seymour Ginsburg a Sheila Greibach, „Abstraktní rodiny jazyků“ , na osmém výročním sympoziu o teorii přepínání a automatů, 18. – 20. října 1967, Austin, Texas, USA , IEEE,1967, str. 128-139
(en) Seymour Ginsburg , Algebraické a automatické teoretické vlastnosti formálních jazyků , Severní Holandsko,1975( ISBN 0-7204-2506-9 )
(en) John E. Hopcroft a Jeffrey D. Ullman, Úvod do teorie automatů, jazyků a výpočtů , Addison-Wesley,1979( ISBN 0-201-02988-X ) , „Kapitola 11: Uzavírací vlastnosti rodin jazyků“
(en) Alexandru Mateescu a Arto Salomaa , „Kapitola 4: Aspekty teorie klasického jazyka“ , G. Rozenberg, A. Salomaa (eds), Handbook of Formal Languages , sv. 1: Word, Language, Grammar , Springer Verlag,1997( ISBN 978-3540604204 ) , str. 175-252

Podívejte se také