Defining strictly local automata, Theory of Computation

Assignment Help:

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define particular, given languages. Towards that end, note that a strictly 2-local automaton can require a particular symbol to appear at the beginning or end of the string and it can permit particular pairs of symbols to occur in the interior of the string but, in general, it can't require an arbitrary pair of symbols to occur in the interior of the string. Consider, for example the language:

639_De?ning Strictly Local Automata.png

This is just the set of all strings over {a, b} in which the sequence ‘ab' occurs at least once. Since the string aabaa is in L1, any strictly 2-local automaton will have to include at least the pairs:

fia, aa, ab, ba, afi.

But then the string aaaaa will also be accepted, using just the first two and the last one of these pairs. Roughly, as long as we have to permit other pairs starting with ‘a' we cannot require ‘ab' to occur.


Related Discussions:- Defining strictly local automata

Closure properties of recognizable languages, We got the class LT by taking...

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also

Myhill graphs, Another way of representing a strictly 2-local automaton is ...

Another way of representing a strictly 2-local automaton is with a Myhill graph. These are directed graphs in which the vertices are labeled with symbols from the input alphabet of

Mealy machine, Construct a Mealy machine that can output EVEN or ODD Accord...

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ...

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Decidability, examples of decidable problems

examples of decidable problems

Discrete math, Find the Regular Grammar for the following Regular Expressio...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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

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