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
We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

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

s-> AACD A-> aAb/e C->aC/a D-> aDa/bDb/e

How useful is production function in production planning?


I want a proof for any NP complete problem

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

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