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 SL₂ automata.

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

Ask an Expert

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

Write your message here..

Related Questions

Sketch an algorithm to recognize the language, First model: Computer has a ... First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

First model of computation, Computer has a single unbounded precision count... Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

Qbasic, Ask question #Minimum 100 words accepte Ask question #Minimum 100 words accepte

Finiteness problem for regular languages, The fact that the Recognition Pro... The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

Universality problem, The Universality Problem is the dual of the emptiness... The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Computation and languages, When we study computability we are studying prob... When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

Language accepted by a nfa, The language accepted by a NFA A = (Q,Σ, δ, q 0... The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

Formal language theory, This was one of the ?rst substantial theorems of Fo... 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

Graph Connectivity, Let G be a graph with n > 2 vertices with (n2 - 3n + 4)... Let G be a graph with n > 2 vertices with (n2 - 3n + 4)/2 edges. Prove that G is connected.

Dfa to re, c program to convert dfa to re c program to convert dfa to re