Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language.

Is there a subclass, say $C$, of deterministic context-free (DCF) languages over $X$ such that if $L \in C$, then $ X^{\ast}LX^{\ast} \in C$ and the generating function of $L$ is a non-rational (algebraic) function?

How can one describe a DCF grammar of $ X^{\ast}LX^{\ast}$, for $L\in C$?

  • 1
    $\begingroup$ In other words, you are looking for a DCFL language $L$ such that $X^*LX^*$ is also DCFL. If you find such a language, then $C = \{L,X^*LX^*\}$ is a solution. Conversely, if you take any $L \in C$, then $X^*LX^* \in C$ and so both $L$ and $X^*LX^*$ are DCFL. $\endgroup$ – Yuval Filmus Mar 7 '18 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.