Strictly k-local automata, Theory of Computation

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the 2-factors to k-factors. We now have the possibility that the scanning window is actually longer than the augmented string. To accommodate that, we will permit factors of any length up to k as long as they start with ‘x' and end with ‘x' as well as k-factors which may or may not start with ‘x' or end with ‘x'.

So a strictly k-local automaton is just an alphabet and a set of stings of length k in which the ?rst symbol is either x or a symbol of the alphabet and the last is either x or a symbol of the alphabet, plus any number of strings of length no greater than k in which the ?rst and last symbol are x and x, respectively. In scanning strings that are shorter than k - 1, the automaton window will span the entire input (plus the beginning and end symbols). In that case, it will accept i? the sequence of symbols in the window is one of those short strings.

You should verify that this is a generalization of SL2 automata, that if k = 2 the de?nition of SLk automata is the same as the de?nition of SL2 automata.

Posted Date: 3/22/2013 1:20:24 AM | Location : United States







Related Discussions:- Strictly k-local automata, Assignment Help, Ask Question on Strictly k-local automata, Get Answer, Expert's Help, Strictly k-local automata Discussions

Write discussion on Strictly k-local automata
Your posts are moderated
Related Questions
Since the signi?cance of the states represented by the nodes of these transition graphs is arbitrary, we will allow ourselves to use any ?nite set (such as {A,B,C,D,E, F,G,H} or ev

Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?


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


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 Clo

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

build a TM that enumerate even set of even length string over a

design an automata for strings having exactly four 1''s