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

Use of Myhill-Nerode Theorem to prove minimal number of states

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

Problem

I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\{a, b}\}$ and $C_k=Σ^*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C_k$ with fewer than $2^k$ states.

Solution

You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.

Context

StackExchange Computer Science Q#81660, answer score: 2

Revisions (0)

No revisions yet.