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
design a turing machine that accepts the language which consists of even number of zero''s and even number of one''s?

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via


Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

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

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

build a TM that enumerate even set of even length string over a


Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi