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
We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Rubber shortnote

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}

Describe the architecture of interface agency

For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N