CMI2017-B-3

Question

Let $Σ = \{a, b\}$. Given words $u, v \in  Σ*$ , we say that $v$ extends $u$ if $v$ is of the form $xuy$ for some $x, y ∈ Σ^*$ . Given a fixed word $u$, we are interested in identifying whether a finite state automaton accepts some word that extends $u$.

Describe an algorithm that takes as input a finite state automaton (DFA or NFA) $\mathcal{A}$ over $Σ = \{a, b\}$ and a word $u ∈ Σ^*$  and reports “Yes” if some word in the language of $\mathcal{A}$ extends $u$ and “No” if no word in the language of $\mathcal{A}$ extends $u$.

Answer 1