Detail publikace

Generalized One-Sided Forbidding Grammars

MEDUNA, A.; ZEMEK, P. Generalized One-Sided Forbidding Grammars. International Journal of Computer Mathematics, 2013, vol. 90, no. 2, p. 172-182. ISSN: 0020-7160.
Název česky
Zobecněné jednostranné zakazující gramatiky
Typ
článek v časopise
Jazyk
anglicky
Autoři
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Zemek Petr, Ing., Ph.D.
URL
Klíčová slova

formální jazyky, řízené přepisování, zobecněné jednostranné zakazující gramatiky, jazykové třídy, generativní síla

Abstrakt

V zobecněných jednostranných zakazujících gramatikách má každé pravidlo přiřazenu konečnou množinu řetězců a množina pravidel je rozdělena na množiny levě a pravě zakazujících pravidel. Levě zakazující pravidlo může být aplikováno pokud každý z jeho zakazujících řetězců není přítomen vlevo od přepisovaného neterminálu v aktuální větné formě. Pravě zakazující pravidlo je aplikováno analogicky. Mimo tohoto pracují jako zobecněné zakazující gramatiky. V článku jsou dokázány následující tři výsledky. (1) Zobecněné jednostranné zakazující gramatiky, kde každý zakazující řetězec je tvořen nejvýše dvěma symboly, definují třídu rekurzivně spočetných jazyků. (2) Zobecněné jednostranné zakazující gramatiky, kde jedna z množin pravidel obsahuje pouze bezkontextová pravidla bez zakazujících řetězců, definují třídu bezkontextových jazyků. (3) Zobecněné jednostranné zakazující gramatiky, kde je množina levě zakazujících pravidel identická s množinou pravě zakazujících pravidel, definují třídu bezkontextových jazyků.

Rok
2013
Strany
172–182
Časopis
International Journal of Computer Mathematics, roč. 90, č. 2, ISSN 0020-7160
DOI
10.1080/00207160.2012.723703
BibTeX 
@article{BUT103403,
  author="Alexandr {Meduna} and Petr {Zemek}",
  title="Generalized One-Sided Forbidding Grammars",
  journal="International Journal of Computer Mathematics",
  year="2013",
  volume="90",
  number="2",
  pages="172--182",
  doi="10.1080/00207160.2012.723703",
  issn="0020-7160",
  url="http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.723703"
}
Nahoru