Absztrakt nyelvcsalád
Az elméleti számítógép-tudomány és különösen elmélet formális nyelvek , a kifejezés absztrakt nyelv család kifejezés olyan fogalom, amely általánosítja közös jellemzői racionális nyelve , az algebrai nyelv , hogy rekurzívan felsorolható nyelvek és sok más család formális nyelvek.
Definíciók
- A hivatalos nyelv egy sor a szavak, mint egy véges ábécé , vagyis egy része a szabad monoid , ahol * jelöli Kleene csillaga .
- A nyelvcsalád egy pár kialakítva végtelen ábécé jelöljük , és bármely véges része az , egy sor formális nyelvek .
- A racionális kúp ( angolul teljes triónak hívják ) a zárt nyelvek családja a morfizmus, az inverz morfizmus és a racionális nyelvekkel való metszés műveleteihez.
- A hű racionális kúp ( angolul triónak hívják ) a zárt nyelvek családja a nem törlő morfizmus, az inverz morfizmus és a racionális nyelvekkel való metszés műveleteihez.
- Egy nyelvcsalád ésszerűen bezárul, ha az unió, a termék és a Kleene csillag műveletei miatt bezárják .
- Az elvont nyelvcsalád ( teljes elvont nyelvcsalád vagy teljes AFL angolul) racionális kúp, amely ráadásul racionálisan zárt.
- Az absztrakt családi hűséges nyelvek ( absztrakt nyelvcsalád vagy angolul AFL ) ésszerűen zárt hű racionális kúp.
Találkozunk a semi-AFL fogalmával is , amely az unió által lezárt racionális kúpot jelenti.
Példák absztrakt nyelv- és tulajdonságcsaládokra
- A racionális nyelvek absztrakt nyelvcsaládot alkotnak.
- Az algebrai nyelvek absztrakt családokat alkotnak.
- A kontextusérzékeny nyelvek absztrakt, családihű nyelveket alkotnak, mivel semmiféle morfizmus nem zárja le őket.
- A rekurzív módon megszámlálható nyelvek a hű nyelvek és a rekurzív nyelvek elvont családját alkotják .
- Minden racionális kúp tartalmazza a racionális nyelvek családját.
- A lineáris nyelvek unió által lezárt racionális kúpot alkotnak. Hasonlóképpen, a kvázi racionális nyelvek unió által lezárt racionális kúpot alkotnak. A lineáris nyelvek nem racionálisan zártak, a kváziracionális nyelvek igen.
- Az egyéb műveleteket nem fejezik ki racionális transzdukciós műveletek vagy racionális műveletek lezárása útján. Ezek különösen a keverés , a tükörkép, a helyettesítések.
Eredet
Az első, absztrakt nyelvcsaládokkal foglalkozó tanulmányt Seymour Ginsburg és Sheila Greibach mutatta be a kapcsolás és az automata elmélet szimpóziumának nyolcadik szimpóziumán 1967-ben.
Megjegyzések
- (en) Ginsburg és Greibach (1967) .
Hivatkozások
- en) Seymour Ginsburg és Sheila Greibach, „A nyelvek absztrakt családjai” , a kapcsolás és az automata elmélet nyolcadik éves szimpóziumán, 1967. október 18–20., Austin, Texas, USA , IEEE,1967, P. 128-139
- en) Seymour Ginsburg , A formális nyelvek algebrai és automata elméleti tulajdonságai , Észak-Hollandia,1975( ISBN 0-7204-2506-9 )
- (en) John E. Hopcroft és Jeffrey D. Ullman, Bevezetés az automata elméletbe, a nyelvek és a számításokba , Addison-Wesley,1979( ISBN 0-201-02988-X ) , "11. fejezet: A nyelvcsaládok bezárási tulajdonságai"
- (en) Alexandru Mateescu és Arto Salomaa , „4. fejezet: A klasszikus nyelvelmélet szempontjai” , G. Rozenberg, A. Salomaa (szerkesztõk), Formális nyelvek kézikönyve , vol. 1: Szó, nyelv, nyelvtan , Springer Verlag,1997( ISBN 978-3540604204 ) , p. 175-252