Michael Sipser Solutions: Sipser 1.62: Dk be the language consisting of all strings that have at least one 'a' among last k symbols. Thus Dk = Σ* a (Σ ∪ ε)k-1 , Give a DFA with at most k+1 states which accepts this language.

Friday 27 September 2013

Sipser 1.62: Dk be the language consisting of all strings that have at least one 'a' among last k symbols. Thus Dk = Σ* a (Σ ∪ ε)^k-1 , Give a DFA with at most k+1 states which accepts this language.

Sipser 1.62: D_k be the language consisting of all strings that have at least one 'a' among last k symbols.
Thus D_k = Σ^*a (Σ ∪ ε)^k-1 , Give a DFA with at most k+1 states which accepts this language.

Solution:

1 comment:

later17 September 2015 at 15:15
The very top edge, this that an "a" transition?
Just make sure this is a DFA.
ReplyDelete
Replies

Add comment