scientific article; zbMATH DE number 223334

From MaRDI portal
Publication:5285978





The customary language-theoretic left (right) derivative of a word \(u\) with respect to a word \(v\) means the deletion of \(v\) from the beginning (end) of \(u\). The natural generalization where \(v\) can be deleted from an arbitrary position in \(u\), is investigated. The resulting operation, denoted by \(\partial_ vu\), is called derivative and it can be extended to languages in the usual fashion. Besides closure properties of the families of the Chomsky hierarchy under derivatives, some properties of the derivatives of regular languages are studied. A sufficient condition under which a language gives rise to the same derivative with respect to two different words is obtained. Moreover, it is shown that the language consisting of all words, with respect to which a given regular language has the same derivative, is regular. Also languages with maximal numbers of derivatives are studied. The main result shows that, for each integer \(n\), there exists a minimal finite deterministic automaton with \(n\) states, which recognizes a language with maximal number of derivatives. Finally, the decision problem ``Given languages L and R, does there exist a word \(w\) such that \(\partial_ wL=R\)? is considered. The problem turns out to be decidable for regular languages L and R, but undecidable for more complex families of languages.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5285978)