Left Quotients of Deterministic Context-Free Languages
摘要
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.