Indexovaný jazyk - Indexed language

Indexované jazyky jsou třídou formální jazyky objeveno uživatelem Alfred Aho;[1] jsou popsány indexované gramatiky a lze je rozpoznat vnořené automaty zásobníku.[2]

Indexované jazyky jsou a správná podmnožina z kontextově citlivé jazyky.[1] Jsou kvalifikovány jako abstraktní rodina jazyků (dále plný AFL), a tudíž uspokojují mnoho uzavíracích vlastností. Nejsou však uzavřeny pod křižovatkou nebo doplňkem.[1]

Třída indexovaných jazyků má praktický význam v zpracování přirozeného jazyka jako výpočetně dostupné[Citace je zapotřebí ] zobecnění bezkontextové jazyky, od té doby indexované gramatiky může popsat mnoho nelokálních omezení vyskytujících se v přirozených jazycích.

Gerald Gazdar (1988)[3] a Vijay-Shanker (1987)[4] představil a mírně citlivý jazyk třída nyní známá jako lineární indexované gramatiky (LIG).[5] Lineární indexované gramatiky mají vůči IG další omezení. LIGy jsou slabě ekvivalentní (vygenerovat stejnou jazykovou třídu) jako strom sousední gramatiky.[6]

Příklady

Následující jazyky jsou indexovány, ale nejsou bez kontextu:

[3]
[2]

Tyto dva jazyky jsou také indexovány, ale nejsou rovnoměrné mírně kontextově citlivé podle Gazdarovy charakterizace:

[2]
[3]

Na druhou stranu není indexován následující jazyk:[7]

Vlastnosti

Hopcroft a Ullman mají tendenci považovat indexované jazyky za „přirozenou“ třídu, protože jsou generovány několika formalizmy, například:[9]

Hayashi[14] zobecnil čerpací lemma naopak indexované gramatiky. Naopak Gilman[7] dává "zmenšující se lemma" pro indexované jazyky.

Viz také

Reference

  1. ^ A b C d Aho, Alfred (1968). "Indexované gramatiky - rozšíření bezkontextových gramatik". Deník ACM. 15 (4): 647–671. doi:10.1145/321479.321488. S2CID  9539666.
  2. ^ A b C Partee, Barbara; ter Meulen, Alice; Wall, Robert E. (1990). Matematické metody v lingvistice. Kluwer Academic Publishers. 536–542. ISBN  978-90-277-2245-4.
  3. ^ A b C Gazdar, Gerald (1988). "Použitelnost indexovaných gramatik na přirozené jazyky". V Reyle, U .; Rohrer, C. (eds.). Rozbor přirozeného jazyka a lingvistické teorie. Studium lingvistiky a filozofie. 35. Springer Nizozemsko. str. 69–94. doi:10.1007/978-94-009-1337-0_3. ISBN  978-94-009-1337-0.
  4. ^ Vijayashanker, K. (1987). Studie stromů navazujících na gramatiky (Teze). ProQuest  303610666.
  5. ^ Kallmeyer, Laura (2010). Analýza nad rámec bezkontextových gramatik. Springer. p. 31. ISBN  978-3-642-14846-0.
  6. ^ Kallmeyer, Laura (16. srpna 2010). Analýza nad rámec bezkontextových gramatik. Springer. p. 32. ISBN  978-3-642-14846-0.
  7. ^ A b Gilman, Robert H. (1996). "Zmenšující se lemma pro indexované jazyky". Teoretická informatika. 163 (1–2): 277–281. arXiv:matematika / 9509205. doi:10.1016/0304-3975(96)00244-7. S2CID  14479068.
  8. ^ Hopcroft, Johne; Ullman, Jeffrey (1979). Úvod do teorie automatů, jazyků a výpočtů. Addison-Wesley. p. 390. ISBN  978-0-201-02988-8.
  9. ^ Úvod do teorie automatů, jazyků a výpočtů,[8] Bibliografické poznámky, s. 394-395
  10. ^ Aho, Alfred V. (červenec 1969). "Vnořené automaty zásobníku". Deník ACM. 16 (3): 383–406. doi:10.1145/321526.321529. S2CID  685569.
  11. ^ Fischer, Michael J. (říjen 1968). Gramatiky s makropodobnými produkcemi. 9. výroční sympozium o teorii přepínání a automatů (SWAT 1968). str. 131–142. doi:10.1109 / SWAT.1968.12.
  12. ^ Greibach, Sheila A. (březen 1970). "Plné AFL a vnořené iterované náhrady". Informace a kontrola. 16 (1): 7–35. doi:10.1016 / s0019-9958 (70) 80039-0.
  13. ^ Maibaum, T.S.E. (Červen 1974). "Zobecněný přístup k formálním jazykům". Journal of Computer and System Sciences. 8 (3): 409–439. doi:10.1016 / s0022-0000 (74) 80031-0.
  14. ^ Hayashi, Takeshi (1973). „Na odvozovacích stromech indexovaných gramatik: rozšíření věty {$ uvwxy $} - věta“. Publikace Výzkumného ústavu pro matematické vědy. 9 (1): 61–92. doi:10,2977 / prims / 1195192738.

externí odkazy