Question

Let $\mathbf{\Sigma }\mathbf{=}\mathbf{\{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{\}}\mathbf{.}$For each $\mathbf{k}\mathbf{\ge }\mathbf{1}$, let role="math" localid="1660750960062" ${\mathbf{D}}_{\mathbf{k}}$be the language consisting of all strings that have at least one a among the last k symbols. Thus ${\mathbf{D}}_{\mathbf{k}}\mathbf{=}\mathbf{\Sigma }\mathbf{*}\mathbf{a}{\mathbf{(}\mathbf{\Sigma }\mathbf{\cup }\mathbf{\epsilon }\mathbf{)}}^{\mathbf{k}\mathbf{-}\mathbf{1}}\mathbf{.}$Describe a DFA with at most $\mathbf{k}\mathbf{+}\mathbf{1}$states that recognizes ${\mathbf{D}}_{\mathbf{k}}$ in terms of both a state diagram and a formal description.

Short answer

Deterministic finite automaton for this language is given below.

Step-by-step solution

Deterministic finite automaton.

Deterministic finite automata (or DFA) are finite state machines that accept or reject strings of characters by parsing them through a sequence that is uniquely determined by each string.

Deterministic finite automaton and its state diagram.

${\mathrm{D}}_{\mathrm{k}}$be the language consisting of all strings that have at least one$\text{'}\mathrm{a}\text{'}$ among last$\mathrm{k}$ symbols.

Fig: Deterministic finite automaton

Thus${\mathrm{D}}_{\mathrm{k}}=\mathrm{\Sigma }*\mathrm{a}{(\mathrm{\Sigma }\cup \mathrm{\epsilon })}^{\mathrm{k}-1}.$, and a DFA deterministic finite automaton with at most$\mathrm{k}+1$ states which accepts this language.