Question

Suppose that L is a regular language. Prove that the language p r e f i x (L )={w | $\exists$ x, wx $\epsilon$ L } is regular. (For example, if L = {abc, def}, prefix(L) = {?, a, ab, abc, d, de, def}.)

Answer 1

prefix(x) : any string that is initial substring of string x is known as prefix of string x.

e.g : for x= abab , prefix strings are : a, ab, aba, abab

Prefix(L) : Prefix language of language L can be defined as set of all prefix of all strings of language L.

----------------------------------------------------------------------------------------------------------------------------------------------------------

if L is regular language , then there exist DFA(deterministic finite automata) for language L. lets say DFA D recognize given regular language L.

Now create new dfa D' such that:

- it has transition function and all states similar to D.

- for each state s ∈ D, if there's an accepting state reachable from s in D, then the corresponding state in D′ will be an accepting state.

here D' will accept the language Prefix(L).

hence we can create DFA for Prefix(L) using DFA of L.

so we can say that Prefix(L) is also regular language if L is regular.

if there is any doubt regarding question then you can ask in comment section.