Defining strictly local automata, Theory of Computation

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.

Posted Date: 3/21/2013 5:51:00 AM | Location : United States







Related Discussions:- Defining strictly local automata, Assignment Help, Ask Question on Defining strictly local automata, Get Answer, Expert's Help, Defining strictly local automata Discussions

Write discussion on Defining strictly local automata
Your posts are moderated
Related Questions
A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

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

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

turing machine for prime numbers