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

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

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

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 Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

design a tuning machine for penidrome

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

Describe the architecture of interface agency

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a