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 u₁, v₁, u₂, and v₂ in Σ* and all strings x in Σ^k-1 :

u₁xv₁ ∈ L and u₂xv₂ ∈ L ⇒ u₁xv₂ ∈ 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

Ask an Expert

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

Write your message here..

Related Questions

Automata, how to prove he extended transition function is derived from part... how to prove he extended transition function is derived from part 2 and 3

Powerset construction, As de?ned the powerset construction builds a DFA wit... As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

Equivalence problem, The Equivalence Problem is the question of whether two... The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Rubber, Rubber shortnote Rubber shortnote

Operations on strictly local languages, The class of Strictly Local Languag... The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

TRANSPORTATION, DEGENERATE OF THE INITIAL SOLUTION DEGENERATE OF THE INITIAL SOLUTION

Closure properties of recognizable languages, We got the class LT by taking... We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

Pushdown automator, draw pda for l={an,bm,an/m,n>=0} n is in superscript draw pda for l={an,bm,an/m,n>=0} n is in superscript

Myhill-nerode, Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff... Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every recogn

Automata, As we are primarily concerned with questions of what is and what ... 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