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
Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi



write short notes on decidable and solvable problem

We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

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

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

what exactly is this and how is it implemented and how to prove its correctness, completeness...

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