Počet záznamů: 1
On restricted context-free grammars
- 1.
SYSNO ASEP 0367493 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název On restricted context-free grammars Tvůrce(i) Dassow, J. (DE)
Masopust, Tomáš (MU-W) RID, ORCID, SAIZdroj.dok. Journal of Computer and System Sciences. - : Elsevier - ISSN 0022-0000
Roč. 78, č. 1 (2012), s. 293-304Poč.str. 12 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova context-free grammars ; derivation restriction ; normal forms Vědní obor RIV BA - Obecná matematika CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000297833200021 EID SCOPUS 81955160869 DOI 10.1016/j.jcss.2011.05.008 Anotace Context-free grammars are widely used for the simple form of their rules. A derivation step consists of the choice of a nonterminal of the sentential form and of an application of a rule rewriting it. Several regulations of the derivation process have been studied to increase the power of context-free grammars. In the resulting grammars, however, not only the symbols to be rewritten are restricted, but also the rules to be applied. In this paper, we study context-free grammars with a simpler restriction where only symbols to be rewritten are restricted, not the rules, in the sense that any rule rewriting the chosen nonterminal can be applied. We prove that these grammars have the same power as random context, matrix, or programmed grammars. We also present two improved normal forms and discuss the characterization of context-sensitive languages by a variant using strings of length at most two instead of symbols. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2012
Počet záznamů: 1