Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly construct the DFA transitions, and not create an NFA first and then convert it to a DFA. In other words, the algorithm accepts the suffix as input, constructs the transitions for each state and then process the input string.

Ex 1: Language: {a,b}, Suffix- abab, Accepted Strings - bbbabab, aaabbabab Ex 2: Language: {a,b}, suffix- babab - Accepted Strings - bababab, aababab

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – dkaeae Feb 5 at 10:24
  • $\begingroup$ The KMP string matching algorithm works this way. $\endgroup$ – Yuval Filmus Feb 5 at 10:29
  • $\begingroup$ Tue KMP algorithm does not provide transitions $\endgroup$ – Saksham Gupta Feb 6 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.