0

I'm struggling with figuring out which one of these languages is guaranteed to be a DCFL, i have two languages to choose from and the word guaranteed is throwing me off. Here are the two languages:

Let f1(L) = {w : wa ∈ L for some a ∈ Σ}
f2(L) = {w : aw ∈ L for some a ∈ Σ}.

Now my my thoughts are that f2 is guaranteed to be Deterministic because it starts with a state directly "a". Therefore right away it has a decided state, any thoughts?

drocktapiff
  • 55

1 Answers1

0

I am assuming that this is a question about closure properties of deterministic context-free languages. So let $L$ be a DCFL.

Now $f1(L)$ is again DCFL, as this class is closed under quotients by regular languages: for regular $R$ also $L/R = \{ w \mid wy \in L \mbox{ for some } y\in R \}$ is DCFL.

On the other hand $f2(L)$ is not necessarily DCFL. The operation basically drops the first letter of a string. This letter can be used to distinguish between two possible computations.

Hendrik Jan
  • 1,910