Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars(Automata and Formal Language Theory)

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents the analogical conception of Chomsky normal form and Greibach normal form for linear, monadic context-free tree grammars (LM-CFTGs). LM-CFTGs generate the same class of languages as four well-known mildly context-sensitive grammars. It will be shown that any LM-CFTG can be transformed into equivalent ones in both normal forms. As Chomsky normal form and Greibach normal form for context-free grammars (CFGs) play a very important role in the study of formal properties of CFGs, it is expected that the Chomsky-like normal form and the Greibach-like normal form for LM-CFTGs will provide deeper analyses of the class of languages generated by mildly context-sensitive grammars.

• 社団法人電子情報通信学会の論文
• 2006-12-01

著者

• Fujiyoshi Akio

  Department Of Computer And Information Sciences Ibaraki University

関連論文

• Minimum Spanning Tree Problem with Label Selection
• The Relation between Unary Parameter Macro Tree Transducers and Spine Grammars
• Multi-Phase Tree Transformations
• Analogical Conception of Chomsky Normal Form and Greibach Normal Form for Linear, Monadic Context-Free Tree Grammars(Automata and Formal Language Theory)
• Application of the CKY Algorithm to Recognition of Tree Structures for Linear, Monadic Context-Free Tree Grammars(Formal Languages,Foundations of Computer Science)
• Linear-Time Recognizable Classes of Tree Languages by Deterministic Linear Pushdown Tree Automata

スポンサーリンク