ON EQUAL MATRIX LANGUAGES

被引:43
作者
SIROMONE.R
机构
[1] Madras Christian College, Tambaram
来源
INFORMATION AND CONTROL | 1969年 / 14卷 / 02期
关键词
D O I
10.1016/S0019-9958(69)90050-3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
A generative grammar called equal matrix grammar which generates a class which meets both context-sensitive and context-free languages is defined and the formal power series generated by context-free grammars is extended to grammars of this system. The Parikh mapping of this family of languages is shown to be semilinear. The Boolean and closure properties of a certain subfamily are examined. For this subfamily, the generative power of equal matrix grammar is higher than that of context-free grammars. For certain inherently ambiguous context-free languages, including that of Parikh, unambiguous grammars of this class exist. The application of equal matrix grammar to the generation of Tamil kernel sentences is given in the appendix. © 1969 Academic Press, Inc.
引用
收藏
页码:135 / &
相关论文
共 10 条
[1]  
ABRAHAM S, 1965, INT C COMPUTATIONAL
[2]  
BRAFFORT P, 1963, COMPUTER PROGRAMM ED, P118
[3]  
BUSH RR, 1963, HANDBOOK MATHEMAT ED, V2
[4]  
Chomsky N., 1959, INFORM CONTROL, V2, P137, DOI 10.1016/S0019-9958(59)90362-6
[5]  
Chomsky N., 1963, COMPUTER PROGRAMMING, P118
[6]  
CHOMSKY N, 1963, HANDBOOK MATHEMATICA, V2
[7]  
GINSBURG S, 1966, MATHEMATICAL THEORY
[8]   INHERENT AMBIGUITY OF MINIMAL LINEAR GRAMMARS [J].
GROSS, M .
INFORMATION AND CONTROL, 1964, 7 (03) :366-&
[9]  
PARIKH R, 1966, J ASSOC COMPUT MACH, V13, P517
[10]  
Scheinberg S, 1960, INFORM CONTR, V3, P372, DOI 10.1016/s0019-9958(60)90965