# Computing substring language on automata

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?

• Yes, it's possible, using standard techniques. I suggest spending a few hours on this exercise. – Yuval Filmus Jan 4 '18 at 11:58
• 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. – Indiscrescion Jan 4 '18 at 14:50
• "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. – Raphael Jan 4 '18 at 15:29
• Hint: use left quotients/factors. – Raphael Jan 4 '18 at 15:29