Streszczenie rodziny języków
W teoretycznej informatyki , aw szczególności teorii języków formalnych , termin rodzina języków streszczenie odnosi się do koncepcji, że uogólnia wspólne cechy racjonalnego języka , że języki algebraiczne , aby język rekurencyjnie przeliczalny i wielu innych rodzin języków formalnych.
Definicje
- Formalny język jest zbiorem słów nad skończonym alfabetem , to jest część wolnej monoid , gdzie * oznacza gwiazdę KLEENE użytkownika .
- Rodzina języków to para utworzona z nieskończonej alfabet oznaczony , a dla każdej skończonej części dnia , od zbioru języków formalnych dotyczących .
- Racjonalne stożek (zwane pełne trio w języku angielskim) to rodzina języków zamkniętych dla działalności morfizmu, odwrotnego morfizmu i skrzyżowania z racjonalnych językach.
- Wierny racjonalne stożek (zwane trio w języku angielskim) to rodzina języków zamkniętych dla działalności non-wymazywania morfizmu, odwrotnego morfizmu i skrzyżowania z racjonalnych językach.
- Rodzina języków jest racjonalnie zamknięta, jeśli jest zamknięta dla operacji związkowych, produktowych i gwiazdowych Kleene .
- Streszczenie rodzina języków ( pełna streszczenie rodzina języków lub pełnego AFL w języku angielskim) jest racjonalny stożek, który w dodatku jest racjonalnie zamknięte.
- Streszczenie rodzina języków wierni ( streszczenie rodzina języków lub AFL w języku angielskim) jest racjonalnie zamknięte wierny racjonalne stożek.
Spotykamy się również z pojęciem semi-AFL dla racjonalnego stożka zamkniętego przez związek.
Przykłady abstrakcyjnych rodzin języków i własności
- Te języki racjonalne formy abstrakcyjne rodziny języków.
- Te języki algebraiczne tworzą rodzinę abstrakcyjnych języków.
- Te języki kontekstowe stanowią abstrakcyjny rodzinie języków wiernych, ponieważ nie są one zamknięte przez każdego morfizmu.
- Na język rekurencyjnie przeliczalny formy abstrakcyjne rodziny języków wiernych, jak również języków rekurencyjnych .
- Każdy stożek racjonalny zawiera rodzinę języków racjonalnych.
- Te języki liniowe tworzą racjonalnego stożek zamknięty przez Unię. Podobnie języki quasi-racjonalne tworzą racjonalny stożek zamknięty przez unię. Języki liniowe nie są racjonalnie zamknięte, języki quasi-racjonalne są.
- Inne operacje nie są wyrażane przez racjonalne operacje transdukcji lub zamknięcie dla racjonalnych operacji. Są to w szczególności tasowanie , lustrzane odbicie, podstawienia.
Pochodzenie
Pierwszy artykuł dotyczący abstrakcyjnych rodzin języków został przedstawiony przez Seymoura Ginsburga i Sheilę Greibach na ósmym sympozjum z serii Symposium on Switching and Automata Theory w 1967 roku.
Uwagi
- (en) Ginsburg i Greibach (1967) .
Bibliografia
- (en) Seymour Ginsburg i Sheila Greibach, „Abstract Families of Languages” , na ósmym dorocznym sympozjum na temat przełączania i teorii automatów, 18–20 października 1967 r., Austin, Teksas, USA , IEEE,1967, s. 128-139
- (en) Seymour Ginsburg , Algebraic and Automata Theoretic Properties of Formal Languages , North-Holland,1975( ISBN 0-7204-2506-9 )
- (en) John E. Hopcroft i Jeffrey D. Ullman, Wprowadzenie do teorii automatów, języków i obliczeń , Addison-Wesley,1979( ISBN 0-201-02988-X ) , „Rozdział 11: Właściwości zamykające rodzin języków”
- (en) Alexandru Mateescu i Arto Salomaa , „Chapter 4: Aspects of Classical Language Theory” , w: G. Rozenberg, A. Salomaa (redaktorzy), Handbook of Formal Languages , vol. 1: Słowo, język, gramatyka , wydawnictwo Springer,1997( ISBN 978-3540604204 ) , str. 175-252