Non - sl languages, Theory of Computation

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had to do was to find two strings in which the same sequence of k - 1 adjacent symbols occurred which when cross-spliced witness the failure of suffix substitution closure. Here we have to be prepared for to show that for any k, such a pair of strings exist. Fortunately, we don't have to show that there is a single pair of strings that works for all k, only that for all k there is some pair. In other words, the pairs we use may depend on k. One useful way to organize this is known as an adversary argument. The theorem can be stated formally as:

579_Non - SL Languages.png

The idea is to interpret this as the rules of a game. You are attempting to show that the property does not hold; your adversary is attempting to show that it does. The universally bound variables (∀L) and (∀u , v , u , v , x) are your choices-your plays. The existentially bound variable (∃k) is your adversary's choice-their plays. The game proceeds from the outside of the formula in:

• You choose L the language you intend to prove is not SL.

• Your adversary, claiming that there is a k-local automaton that recognizes it, chooses k. Presumably, their choice of k will depend on your choice of L. Not even this adversary is going to claim that all languages are SL.

• You now choose two strings u1xv1 and u2xv2. Again, your choice should depend on the specific value of k your adversary chose (as well, of course, as the L you chose to start with).

• You win iff the two strings you chose witness that the language does not satisfy the theorem, i.e., iff

- u1xv1 and u2xv2 are both in L and

- u1xv2 is not in L.

Under this interpretation of the theorem, a proof that a given language is non SL consists of a strategy that always leads to a win whenever you start with L as your initial choice.

Posted Date: 3/22/2013 1:49:38 AM | Location : United States







Related Discussions:- Non - sl languages, Assignment Help, Ask Question on Non - sl languages, Get Answer, Expert's Help, Non - sl languages Discussions

Write discussion on Non - sl languages
Your posts are moderated
Related Questions
A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Explain Theory of Computation ,Overview of DFA,NFA, CFG, PDA, Turing Machine, Regular Language, Context Free Language, Pumping Lemma, Context Sensitive Language, Chomsky Normal For

Rubber shortnote

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

how to convert a grammar into GNF

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine


distinguish between histogram and historigram

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.