Strictly k-local automata, Theory of Computation

Assignment Help:

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.


Related Discussions:- Strictly k-local automata

Flow charts, https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%...

https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

Normal forms, how to convert a grammar into GNF

how to convert a grammar into GNF

Automaton for finite languages, We can then specify any language in the cla...

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

Automaton theory, let G=(V,T,S,P) where V={a,b,A,B,S}, T={a,b},S the start ...

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

Gdtr, What is the purpose of GDTR?

What is the purpose of GDTR?

Path function of a nfa, The path function δ : Q × Σ*→ P(Q) is the extension...

The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an

Kleene Closure, 1. Does above all''s properties can be used to prove a lang...

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

Myhill-nerode theorem, The Myhill-Nerode Theorem provided us with an algori...

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

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd