1
$\begingroup$

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

$\endgroup$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.