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

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?

• 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. – Vimal Patel Nov 18 '19 at 2:36

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.