Strictly local generation automaton, Theory of Computation

Assignment Help:

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the

automaton as an inexhaustible set of tiles labeled with the pairs of symbols, infinitely many instances of each type. The generator starts by selecting any tile labeled with 'x' on its left half. It then proceeds by selecting any tile for which the left half symbol matches the symbol on the right half of the previously selected tile and placing it with its left half overlapping the right half of that previous tile. In this way, the sequence of tiles grows until some tile with 'x' on its right half is placed. The generated string is the sequence of exposed symbols, not including the beginning and end symbols. Generation is non-deterministic-at each step the choice of tile is restricted only by the right symbol of the previous tile. A derivation of the generator is just the sequence of choices it makes in assembling a string, a sequence of pairs of symbols. The language generated by the generator is the set of all strings assembled by any of its derivations.

It should be clear that every string assembled by a derivation of the generator will be accepted by the automaton: the computation of the automaton will check the same sequence of pairs as the derivation of the generator uses and each of those pairs will be in the lookup table, hence, the computation will accept. Similarly it should be clear that every string accepted by a computation of the automaton will be assembled by the corresponding derivation of the generator.


Related Discussions:- Strictly local generation automaton

Construct a recognizer, Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG t...

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the sec

Pumping lemma, For every regular language there is a constant n depending o...

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

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}

Can you help me in automata questions, i have some questions in automata, c...

i have some questions in automata, can you please help me in solving in these questions?

Construct a regular expression, Given any NFA A, we will construct a regula...

Given any NFA A, we will construct a regular expression denoting L(A) by means of an expression graph, a generalization of NFA transition graphs in which the edges are labeled with

Equivalence of nfas and dfas, In general non-determinism, by introducing a ...

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Agents architecture, Describe the architecture of interface agency

Describe the architecture of interface agency

Strictly local languages, We have now de?ned classes of k-local languages f...

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general. De?nition (Strictly Local Languages) A langu

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