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

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

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

Problem

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.

I am trying to find an example of such a DFA, any help?

Solution

This is related to the usual NFA to DFA complexity problem. Strings over $\{a,b\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|>1$.

Context

StackExchange Computer Science Q#18648, answer score: 5

Revisions (0)

No revisions yet.