On the Power of Permitting Semi-conditional Grammars

被引：5

作者：

Gazdag, Zsolt ^{[1
]}

Tichler, Krisztian ^{[2
]}

机构：

[1] Univ Szeged, Dept Fdn Comp Sci, Szeged, Hungary

[2] Eotvos Lorand Univ, Dept Algorithms & Their Applicat, Budapest, Hungary

来源：

DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017 | 2017年 / 10396卷

关键词：

Conditional grammars; Permitting context; Generative power;

D O I：

10.1007/978-3-319-62809-7_12

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Permitting semi-conditional grammars are such extensions of context-free grammars where each rule is associated with a word upsilon, and such a rule can be applied to a sentential form u only if upsilon is a subword of u. In this paper we show that the class of languages generated by permitting semi-conditional grammars with no erasing rules is strictly included in the class of context-sensitive languages.

引用

页码：173 / 184

页数：12

共 19 条

[1]

[Anonymous], 1985, Studies in Natural Language Processing, DOI [10.1017/CBO9780511597855.007, DOI 10.1017/CBO9780511597855]

[2]

[Anonymous], 1960, Trans. Amer. Math. Soc., DOI DOI 10.1090/S0002-9947-1960-0111704-1

[3]

[Anonymous], 2018, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition

[4]

Bordihn H, 1995, DEV LANGUAGE THEORY

[5]

Dassow J, 1989, REGULATED REWRITING

[6] On restricted context-free grammars [J].

Dassow, Juergen ;

Masopust, Tomas .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (01) :293-304

[7] Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors [J].

Dickson, LE .

AMERICAN JOURNAL OF MATHEMATICS, 1913, 35 :413-422

[8] A pumping lemma for random permitting context languages [J].

Ewert, S ;

van der Walt, A .

THEORETICAL COMPUTER SCIENCE, 2002, 270 (1-2) :959-967

[9]

Gazdag Z, POWER PERMITTING SEM

[10]

Gazdag Z., 2011, P 2010 MIN C APPL TH

← 1 2 →