Sipser 1.63 Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.

Sipser 1.63

(a) Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.

Hint: An infinite regular language must be having a loop in its trasistion diagram for DFA (if complement operation is not given). Unroll the loop to make two DFA, first of which accepts strings which have odd number of iterations of concerned loops and second accepts strings which have even number of iteration of concerned loops.

Now, don't ask me solution u dumbo. this is the solution.

(b) Let B and D be two languages. Write B⊂⊂D if B ⊂ D and D contains infinitely many strings that are not in B. Show that, if B and D are two languages where B⊂⊂D, then we can find a regular language C where B⊂⊂C⊂⊂D.

Solution: by part (a), I can always split D into B and A which both are infinite and disjoint regular subsets. And similarly, I can split A into A₁ and A₂, both of them regular infinite and disjoint. Consider C = B ∪ A₁. Of course C is regular (union of two regular languages is regular) and infinite.
And B,C,D holds B⊂⊂C⊂⊂D true.

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: