cmi2017b
closed

closed by
120 views
0 votes
0 votes
closed as a duplicate of: CMI2017-B-3
Let Σ = {a, b}. Given words u, v ∈ Σ ∗ , 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) A over Σ = {a, b} and a word u ∈ Σ ∗ and reports “Yes” if some word in the language of A extends u and “No” if no word in the language of A extends u.
closed by

No related questions found