Detail publikace

Some Power-Decreasing Derivation Restrictions in Grammar Systems

MEDUNA, A.; ČERMÁK, M.; MASOPUST, T. Some Power-Decreasing Derivation Restrictions in Grammar Systems. Schedae Informaticae, 2011, vol. 2010, no. 19, p. 23-34. ISSN: 0860-0295.
Název česky
Oslabující omezení na derivacích v gramatických systémech
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Čermák Martin, Ing., Ph.D.
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Klíčová slova

Grammar systems, derivation restriction, generative power.

Abstrakt

Článek zavádí levá omezení na derivacích v CD gramatických systémech, s frázově strukturovanými gramatikami, řízených regulárním jazykem. První omezení požaduje, aby každá produkce byla vždy aplikována uvnitř prvních k neterminálů, pro nějaké k=1,...,n, v každé větné formě. Druhé omezení říká kolik bloků neterminálů může být v každé větné formě. Třetí omezení rozšiřuje druhé a říká kolik bloků neterminálů s limitovanou délkou může být v každé větné formě. Ukážeme, že nad těmito omezeními gramatické systémy generují různé rodiny jazyků. 

Rok
2011
Strany
23–34
Časopis
Schedae Informaticae, roč. 2010, č. 19, ISSN 0860-0295
Kniha
Schedae Informaticae
BibTeX 
@article{BUT76285,
  author="Alexandr {Meduna} and Martin {Čermák} and Tomáš {Masopust}",
  title="Some Power-Decreasing Derivation Restrictions in Grammar Systems",
  journal="Schedae Informaticae",
  year="2011",
  volume="2010",
  number="19",
  pages="23--34",
  issn="0860-0295"
}
Nahoru