Normal Forms for Uniquely Parsable Grammar Classes Forming the Deterministic Chomsky Hierarchy

スポンサーリンク

概要

• 論文の詳細を見る

• A uniquely parsable grammar (UPG) introduced by Morita et al. is a kind of generative grammer, in which parsing can be performed without backtracking. It is known that UPGs and their three subclasses form the "deterministic Chomsky hierarch." In this paper, we introduce three kinds of normal forms for UPGs, i. e., Type-0, Type-1 and Type-2 UPGs by restricting the forms of rules to very simple ones. We show that the upper three classes in the deterministic Chomsky hierarchy can be exactly characterized by the three types of UPGs.

• 社団法人電子情報通信学会の論文
• 2000-11-25

著者

• Morita Kenichi

  Hiroshima Univ. Higashihiroshima‐shi Jpn

• Morita K

  Hiroshima Univ. Higashi‐hiroshima‐shi Jpn

• Morita Kenichi

  The Authors Are With The Faculty Of Engineering Hiroshima University

• LEE Jia

  The authors are with the Faculty of Engineering, Hiroshima University

• Lee Jia

  The Authors Are With The Faculty Of Engineering Hiroshima University

関連論文

• Uniquely Parallel Parsable Unification Grammars (Special lssue on Selected Papers from LA Synposium)
• Normal Forms for Uniquely Parsable Grammar Classes Forming the Deterministic Chomsky Hierarchy
• On the Non-existance of Rotation-Symmetric von Neumann Neighbor Number-Conserving Cellular Automata of Which the State Number is Less than Four
• A Recursive Padding Technique on Nondeterministic Cellular Automata
• Prefix Computations on Iterative Arrays with Sequential Input/Output Mode(Cellular Automata)
• A Logically Universal Number-Conserving Cellular Automaton with a Unary Table-Lookup Function(Cellular Automata)
• Lower Bound of Face Guards of Polyhedral Terrains

スポンサーリンク