How to determine if a language is deterministic context-free language?

Question

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?

Answer 1

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.