Chomsky-schutzenberger, Theory of Computation

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automaton A accepts w iff the run of A on w ends in an accepting state. (If A is non-deterministic there will potentially be many runs with the automaton accepting if any one of them ends in an accepting state.) Note that the set of runs of an automaton is an SL2 language, recognized by the SL2 automaton (over Q) one gets by projecting away the third component of the triples of GA. Thus there is some kind of close relationship between the strictly local languages and the recognizable languages.

To get at this we will start by working in the other direction, extending our tiles to hold four symbols. The idea is to include, for each tile (q, p, σ) ∈ GA, a tile extended with σ′ for each σ′ ∈ Σ. (We don't actually need tiles for all such σ′ , only for those that occur on tiles (x, q, σ′) which might precede this one in a tiling, but including all of them will be harmless-the ones that do not occur on such tiles will just be useless.)

Posted Date: 3/21/2013 3:39:22 AM | Location : United States







Related Discussions:- Chomsky-schutzenberger, Assignment Help, Ask Question on Chomsky-schutzenberger, Get Answer, Expert's Help, Chomsky-schutzenberger Discussions

Write discussion on Chomsky-schutzenberger
Your posts are moderated
Related Questions
What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

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

Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program


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

I want a proof for any NP complete problem

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

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