Non - sl languages, Theory of Computation

Assignment Help:

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.


Related Discussions:- Non - sl languages

Non - sl languages, Application of the general suffix substitution closure ...

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

DFA, designing DFA

designing DFA

Production, How useful is production function in production planning?

How useful is production function in production planning?

Binary form and chomsky normal form, Normal forms are important because the...

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

Decision problems of regular languages, We'll close our consideration of re...

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Discrete math, Find the Regular Grammar for the following Regular Expressio...

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

Moore machine, Construct a Moore machine to convert a binary string of radi...

Construct a Moore machine to convert a binary string of radix 4.

Third model of computation, Computer has a single LIFO stack containing ?xe...

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

Non Regular, Prove that Language is non regular TRailing count={aa ba aaaa...

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd