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
Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

how many pendulum swings will it take to walk across the classroom?

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

DEGENERATE OF THE INITIAL SOLUTION

The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

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 part