0
$\begingroup$

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes).

I would like to compute, given a DFA, the automaton of the substrings from position i to position j.

For example, given the automaton of L ={ abc, bcd, def }, I would like to compute the automaton of the substrings of L from 1 to 2, i,e. L' = {b,c,d}. Another example, for the language M = {ε ,a, aa, aaa, aaaa, ...}, i,e, a^*, the language of the substrings of M from 0 to 3 should be M' = { ε, a, aa, aaa }.

Starting from the automaton M and i and j, is it possible to compute the automaton of substrings from i to j?

$\endgroup$
  • 2
    $\begingroup$ Yes, it's possible, using standard techniques. I suggest spending a few hours on this exercise. $\endgroup$ – Yuval Filmus Jan 4 '18 at 11:58
  • $\begingroup$ I've tried to use standard techniques and closure properties on regular languages: given an automaton M my idea was to compute Suffix(Prefix(M)) ∩ M_{j-i}, where M_{j-i} is the automaton that recognizes the strings of length j-i. By the way, the resulting automaton recognizes the substrings of length j - i. I'm trying to find out other solutions, still using closure properties. $\endgroup$ – Indiscrescion Jan 4 '18 at 14:50
  • $\begingroup$ "Suffix(Prefix(M)) ∩ M_{j-i}, where M_{j-i} is the automaton that recognizes the strings of length j-i." -- that won't work; you lose the information where the substring was. $\endgroup$ – Raphael Jan 4 '18 at 15:29
  • $\begingroup$ Hint: use left quotients/factors. $\endgroup$ – Raphael Jan 4 '18 at 15:29

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.