Show that there exists an algorithm to determine whether L

Show that there exists an algorithm to determine whether L = * for any regular language L.

Solution

Problem –

Show that there exists an algorithm to determine whether L = * for any regular language L.?

Answer- in this question you are asking about the membership algorithms for regular language

So I am trying to solve your problem.

Solution

Now I write the same question in another way if w is any string and it’s generated from set of input Symbol then we want to prove that if there is any algorithm for determining whether or not w is in L.

Let the DFA (M) define as   M = (Q, , , q0, F)

·         Q is a finite set of states.

·         is a finite set of symbols, called the alphabet of the automaton.

·         is the transition function, that is, : Q × Q.

·         q₀ is the start state, that is, the state of the automaton before any input has been processed, where q₀ Q.

·         F is a set of states of Q (i.e. FQ) called accept states.

Here w is made from set of

Now if L is regular then there exists a DFA/NFA which is equivalent to these languages, means this DFA/NFA must accept some string generated by the language, Now we assume the DFA/NFA = M1 those accept some string generated from this language .

Now if w is generated from then there exists a DFA/NFA which accept the w, called M2,

Now w and L generated from same input symbol and accepted by the machine M1 & M2, so we can say w L

Now we can write

If a DFA = (Q, , , q0, F) is used as a membership criterion, then the set of strings accepted by M is a language. That is,

L (M) = {w *, * (q0, w) F}.