Strictly local languages, Theory of Computation

Assignment Help:

While the SL2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless-the behavior of the automaton depends only on the most recent symbol it has read.

Certainly there are many languages of interest that are not SL2, that will require a more sophisticated algorithm than strictly 2-local automata.

One obvious way of extending the SL2 automata is to give them more memory. Consider, for instance, the language of algebraic expressions over decimal integer constants in which we permit negative constants, indicated by a pre?x ‘-'. Note that this is not the same as allowing ‘-' to be used as a unary operator. In the latter case we would allow any number of ‘-'s to occur in sequence (indicating nested negation), in the case in hand, we will allow ‘-'s to occur only singly (as either a subtraction operator or a leading negative sign) or in pairs (as a subtraction operator followed by a leading negative sign). We will still forbid embedded spaces and the use of ‘+' as a sign.

This is not an SL2 language. If we must permit ‘--' anywhere, then we would have to permit arbitrarily long sequences of ‘-'s. We can recognize this language, though, if we widen the automaton's scanning window to three symbols.


Related Discussions:- Strictly local languages

Computation and languages, When we study computability we are studying prob...

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

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

Possibility of recognizing the palindrome language, Computer has a single F...

Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Strictly local generation automaton, Another way of interpreting a strictly...

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 inexh

Transition graph for the automaton, Lemma 1 A string w ∈ Σ* is accepted by ...

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

Non - sl languages, Application of the general suffix substitution closure ...

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Boolean operations - class of recognizable languages, Theorem The class of ...

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

Decision problems, In Exercise 9 you showed that the recognition problem an...

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

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.

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