Search code examples
regular-languageautomata

Whether this is the general approach for making a DFA for accepting prefix language of a given regular language?


Would it be safe to generalize that if we are given a DFA say M , we can obtain DFA for the prefix language ( Note that prefix language of a given Language consists of all the strings u such that such that uv is an an elements of L and v is an element of $$ \[\sum\textsuperscript{*}] $$ ) by adding all such states of M that have some path to the final state to the set of final states for the new DFA M'. This M' will accept prefix language of L.


Solution

  • Yes, this construction works. To prove this formally, we can argue that the language of your newly constructed automaton (1) is a subset of the prefix language and (2) is a superset of the prefix language. That is, (1) everything in the language of your new automaton is a prefix of a string in the language of the original automaton, and (2) every prefix of a string in the original language is a string in the language of your new automaton. Whenever you want to prove two sets are equal, this is a good (but certainly not the only) method of doing so. Again, two sets are equal if each is both a subset and a superset of the other. We will now prove each of the two necessary claims in turn and then make the desired conclusion.

    Part #1: Every string in the language of your new automaton is a prefix of a string in the language of the original automaton. Suppose this were not the case. That is, your new automaton accepts something that is not a prefix of any string in the original language. Then, the new DFA must have an accepting state which has no path to one of the states which was accepting in the original DFA. But this is a contradiction since, by construction, all of the accepting states in the new DFA have a path to an accepting state in the original DFA. Therefore, our assumption was wrong and it is the case that every string accepted by the new DFA is a prefix.

    Part #2: Every prefix of every string in the original language is accepted by the new DFA. Suppose this were not the case. Then there is some prefix x of a string xy in the original language which is not accepted by the new DFA. Suppose string x leads to state q in the original DFA, and string xy leads to state q' in the original DFA. Because xy is a string in the original language, q' must be accepting. Note that there is a path from q to q' (start in q and process suffix y). Therefore, q must be accepting in the new DFA, and since x led to q in the original DFA, it leads there in the new one as well and must be accepted. This is a contradiction, so it must be the case that all prefixes are accepted.

    Because the new DFA only accepts prefixes, and because it accepts all prefixes, we conclude that it accepts precisely the prefixes of the original language.