patternMinor
Use of Myhill-Nerode Theorem to prove minimal number of states
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.
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.