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

Complement - operations on languages, The fact that SL 2 is closed under i...

The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

Automata and compiler, Automata and Compiler (1) [25 marks] Let N be the...

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Kleenes theorem, All that distinguishes the de?nition of the class of Regul...

All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Prepare the consolidated financial statements, Prepare the consolidated fin...

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

Prove the arden''s theorem, State and Prove the Arden's theorem for Regular...

State and Prove the Arden's theorem for Regular Expression

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

Turing machine , Let ? ={0,1} design a Turing machine that accepts L={0^m ...

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

Assignment, Consider a water bottle vending machine as a finite–state autom...

Consider a water bottle vending machine as a finite–state automaton. This machine is designed to accept coins of Rs. 2 and 5 only. It dispenses a single water bottle as soon as the

Normal forms, how to convert a grammar into GNF

how to convert a grammar into GNF

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