Strictly 2 - local automata, Theory of Computation

Assignment Help:

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.


Related Discussions:- Strictly 2 - local automata

Formal languages and grammar, The universe of strings is a very useful medi...

The universe of strings is a very useful medium for the representation of information as long as there exists a function that provides the interpretation for the information carrie

Define ambiguity in cfg, Define the following concept with an example: a.  ...

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

Chomsky normal form, s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbo...

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

Context free grammar, A context free grammar G = (N, Σ, P, S)  is in binary...

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

Non - sl languages, The key thing about the Suffx Substitution Closure prop...

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

Find a regular expression, Find a regular expression for the regular langua...

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

Mapping reducibility, Can you say that B is decidable? If you somehow know...

Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?

Prism algorithm, what exactly is this and how is it implemented and how to ...

what exactly is this and how is it implemented and how to prove its correctness, completeness...

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.

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