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

Differentiate between dfa and nfa, Differentiate between DFA and NFA. Conve...

Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Kleene closure, So we have that every language that can be constructed from...

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Prepare the consolidated financial statements, Prepare the consolidated fin...

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

Gdtr, What is the purpose of GDTR?

What is the purpose of GDTR?

Normal forms, how to convert a grammar into GNF

how to convert a grammar into GNF

Alphabets - strings and representation, A finite, nonempty ordered set will...

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

Class of local languages is not closed under union, Both L 1 and L 2 are ...

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

Finite languages and strictly local languages, Theorem The class of ?nite l...

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

IT PRoject Management, What are the benefits of using work breakdown struct...

What are the benefits of using work breakdown structure, Project Management

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