Left quotients play a crucial role in automata and formal language theory, but their use on the important class of one-way deterministic pushdown automata (which accept the deterministic context-free languages, \(\textsf{DCFL}\) ) has been understudied. In this paper, we study two novel language families: the family of all \(\textsf{DCFL}\) languages L such that the left quotient of L by any regular language is in \(\textsf{DCFL}\) ; and the smallest family containing \(\textsf{DCFL}\) that is closed under left quotient by regular languages. The first family is properly contained in \(\textsf{DCFL}\) but is powerful enough to accept the Dyck languages and has quite unusual closure properties. Multiple characterizations are given for the second family, including the surprising result that the smallest family containing \(\textsf{DCFL}\) that is closed under left quotient with regular languages is equal to the smallest family containing \(\textsf{DCFL}\) that is closed under union, concatenation, and Kleene- \(*\) . This implies that languages in this family are quite practical as they can all be recognized in linear time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Left Quotients of Deterministic Context-Free Languages

  • Brennan Lockinger,
  • Ian McQuillan

摘要

Left quotients play a crucial role in automata and formal language theory, but their use on the important class of one-way deterministic pushdown automata (which accept the deterministic context-free languages, \(\textsf{DCFL}\) ) has been understudied. In this paper, we study two novel language families: the family of all \(\textsf{DCFL}\) languages L such that the left quotient of L by any regular language is in \(\textsf{DCFL}\) ; and the smallest family containing \(\textsf{DCFL}\) that is closed under left quotient by regular languages. The first family is properly contained in \(\textsf{DCFL}\) but is powerful enough to accept the Dyck languages and has quite unusual closure properties. Multiple characterizations are given for the second family, including the surprising result that the smallest family containing \(\textsf{DCFL}\) that is closed under left quotient with regular languages is equal to the smallest family containing \(\textsf{DCFL}\) that is closed under union, concatenation, and Kleene- \(*\) . This implies that languages in this family are quite practical as they can all be recognized in linear time.