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
Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

In general non-determinism, by introducing a degree of parallelism, may increase the accepting power of a model of computation. But if we subject NFAs to the same sort of analysis

Ask question #Minimum 100 words accepte

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

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be