Local suffix substitution closure, Theory of Computation

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages.

Lemma (k-Local Suffix Substitution Closure) If L is a strictly k-local language then for all strings u1, v1, u2, and v2 in Σ* and all strings x in Σk-1 :

u1xv1 ∈ L and u2xv2 ∈ L ⇒ u1xv2 ∈ L.

The justi?cation is essentially identical to that of our original suffix substitution closure lemma. If L ∈ SLk then it is recognized by an SLk automaton. In the k-local Myhill graph of that automaton, any path from ‘?' to the vertex labeled x can be put together with any path from that vertex to ‘?' to produce a path that represents a string in L.

Posted Date: 3/22/2013 1:32:16 AM | Location : United States







Related Discussions:- Local suffix substitution closure, Assignment Help, Ask Question on Local suffix substitution closure, Get Answer, Expert's Help, Local suffix substitution closure Discussions

Write discussion on Local suffix substitution closure
Your posts are moderated
Related Questions
The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

How useful is production function in production planning?

Rubber shortnote

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

constract context free g ={ a^n b^m : m,n >=0 and n

Computation of a DFA or NFA without ε-transitions An ID (q 1 ,w 1 ) computes (qn,wn) in A = (Q,Σ, T, q 0 , F) (in zero or more steps) if there is a sequence of IDs (q 1