HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Closure of Deterministic context-free languages under prefix

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
prefixfreelanguagesunderdeterministiccontextclosure

Problem

For a formal language $L \subseteq \Sigma^{*}$ I define the set Pref(L) to be:

$\text{pref}(L) = \{\alpha \in \Sigma^{} : \exists \beta \in \Sigma^{} \text{ such that } \alpha \beta \in L\}$

ie. the set of all (not necessarily proper) prefixes of words in $L$. I know that if $L$ is context-free then pref(L) is context-free but if $L$ is deterministic context-free then is pref(L) deterministic context-free?

I am sure this is known but I cannot find the answer anywhere and it's not in Hopcroft and Ullman.

Solution

DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.

Context

StackExchange Computer Science Q#4924, answer score: 9

Revisions (0)

No revisions yet.