We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input alphabet. The automaton starts with the window positioned over the beginning of string marker and the first symbol of the word (if any). At each step, it looks up the pair of symbols in the window in a table of pairs of symbols. It halts when the end of string marker is in the window (if not sooner).

The S-R element is a set/reset latch. It holds the current output which is initially set to TRUE by driving the START input FALSE. (The inverting circle and vinculum over the signal name indicate an input that is activated when it is driven FALSE.) It is then is reset to FALSE if any pair of symbols in the window fails to match some pair in the lookup table (if output of the ‘∈' element ever goes FALSE). Once reset it remains FALSE. Since the output will be FALSE at the end of the string if it ever goes FALSE during the computation, we may just as well assume that the automaton halts when the first pair that is not in the lookup table is encountered.

Formally, all we need do to specify a particular instance of a strictly 2-local automaton is to give the alphabet and list the pairs of symbols in the internal table.

Posted Date: 3/21/2013 5:40:24 AM | Location : United States

Ask an Expert

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

Write discussion on Strictly 2 - local automata
Your posts are moderated

Write your message here..

Related Questions

Tuning machine, design a tuning machine for penidrome design a tuning machine for penidrome

Differentiate between dfa and nfa, Differentiate between DFA and NFA. Conve... Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Recognition problem, The Recognition Problem for a class of languages is th... 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

Exhaustive search, A problem is said to be unsolvable if no algorithm can s... A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

Give a strictly 2-local automaton, Let L 3 = {a i bc j | i, j ≥ 0}. Give ... Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

Michael porter, value chain value chain

Binary form and chomsky normal form, Normal forms are important because the... 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

Sketch an algorithm for recognizing language, Suppose A = (Σ, T) is an SL 2... Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors... The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?} Σ and some factors in Σ {?} distinguishing symbols that may occur at the beginning and en

Regular languages, LTO was the closure of LT under concatenation and Boolea... LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl