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

Techniques to prove a language is not DCFL

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

Problem

I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL.

Are there any other techniques that will help me to prove a language L is not DCFL?

Solution

There is a direct type of argument, related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). Then if one input string is the prefix of another, the computation for the longer string must have the shorter computation as prefix. Thus, the computation accepts at (at least) two moments.

As an example, $\{ a^n b^m \mid n\ge1, m=n \mbox{ or } m=2n \}$ is not DCFL; which is seen as follows.

Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewire $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\{ a^nb^nc^n\mid n\ge 1\}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.

Context

StackExchange Computer Science Q#38242, answer score: 7

Revisions (0)

No revisions yet.