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
A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

what are composition and its function of gastric juice

A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en


When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

what exactly is this and how is it implemented and how to prove its correctness, completeness...


1. Does above all''s properties can be used to prove a language regular? 2..which of the properties can be used to prove a language regular and which of these not? 3..Identify one

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif