4
$\begingroup$

I have the following question to solve : DCFL means Deterministic Context-Free Language.

Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $f(L)$ is a DCFL. Explain your answers.

(a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)

(b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

I tried to find a counterexample to the problem, however I didn't find anything. So I am thinking that it is deterministic. I am wondering how I should approach these kind of questions? and how to determine a language is deterministic?

$\endgroup$
  • 1
    $\begingroup$ for part(b) consider $L=\{a^nb^{2n}\} \cup \{ca^nb^n\}$. Now, $f_2(L) = \{a^{n-1}b^{2n}\} \cup \{a^nb^n\}$. Later is not DCFL. $\endgroup$ – Vimal Patel Nov 18 '19 at 2:36
1
$\begingroup$

Here $L$ is DCFL.

(a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)

Let's define homomorphism $h$ as follow:

$h(a) = a, \space a\in\Sigma$

$h(\epsilon)= c$

$L' = h^{-1}(L) \cap (\Sigma^*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.)

Now start with DPDA of $L'$ and whenever you find $c$ in input make transition to final state.


(b) $f_2(L) = \{v\in\Sigma^*: av\in L\text{ for some }a\in\Sigma\}$ (that is, $f_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

Consider $L=\{a^nb^{2n}\} \cup \{ca^nb^n\}$ Now $f_2(L) = \{a^{n-1}b^{2n}\} \cup \{a^nb^n\}$ Which is not DCFL.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.