4 Show that PrefixLx for some y xy E L is regular if L is re

4. Show that Prefix(L)-x: for some y, xy E L is regular if L is regular

Solution

As L is a regular language it will have a DFA. The new language prefix(L) should accept x if xy (for some y) belongs to L. As we are given that y can be anything, this can be achieved by taking all states which have a path from start and will reach a final state for some string, we make all those states as final states. This DFA will accept a substring of any string accepted by L. Now as prefix(L) has a DFA, it is a regular language.