文献

J-GLOBAL ID：201602020430929907   整理番号：69A0232005

インデクスのある文法 コンテクストフリー文法の一拡張

Indexed grammars An extension of contextfree grammars.

著者 (1件)： AHO A V
資料名： J Assoc Comput Mach  (Journal of the Association for Computing Machinery)
巻： 15  号： 4  ページ： 647-671  発行年： 1968年 
JST資料番号： C0267A  ISSN： 0004-5411  CODEN： JACOA   資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA) 

抄録/ポイント： インデクスまたはフラッグと呼ばれる有限集合をもつこの文法によって生成される言語はCF言語のすべて,およびコンテクストセンシティブ言語(CSL)の一部を含み,CSLのクラスの真の部分クラスである。ユニオン,コンカテネーション,*演算および非決定性有限変換とその逆変換でそれぞれ閉じている。この言語Lが空か,語wを含むかどうかはいずれも決定可能である。制限をつけたインデクス文法による言語はCF言語と等価であることを示す;写図1参16

タイトルに関連する用語 (4件)： インデクス ,  文法 ,  コンテクスト ,  拡張