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
This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start symbol and P={S->Aba, A->BB, B->ab,AB->b} 1.show the derivation sentence for the string ababba 2. find a sentential form

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define part

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.

write short notes on decidable and solvable problem

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

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

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