Input-driven languages are linear conjunctive

详细信息    查看全文

• 作者：Alexander Okhotin¹ ; ^{alexander.okhotin@utu.fi" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Context-free grammars ; Conjunctive grammars ; Cellular automata ; Trellis automata ; Pushdown automata ; Input-driven automata ; Visibly pushdown automata
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：7 March 2016
• 年：2016
• 卷：618
• 期：Complete
• 页码：52-71
• 全文大小：991 K

文摘

Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (A. Okhotin, “On the equivalence of linear conjunctive grammars to trellis automata”, RAIRO ITA, 2004), and this family is known to be incomparable with the context-free languages (V. Terrier, “On real-time one-way cellular array”, Theoret. Comput. Sci.  , 1995). This paper demonstrates the containment of the languages accepted by input-driven pushdown automata (a.k.a. visibly pushdown automata) in the family of linear conjunctive languages, which is established by a direct simulation of an input-driven automaton by a one-way real-time cellular automaton. On the other hand, it is shown that the language families defined by the unambiguous grammars, the LR(k)$\text{LR}(k)$ grammars and the LL(k)$\text{LL}(k)$ grammars are incomparable with the linear conjunctive languages.