Operations on strictly local languages, Theory of Computation

Assignment Help:

The class of Strictly Local Languages (in general) is closed under

• intersection but is not closed under

• union

• complement

• concatenation

• Kleene- and positive closure

Proof: For intersection, we can adapt the construction and proof for the SL2 case again to get closure under intersection for SLk. This is still not quite enough for SL in general, since one of the languages may be in SLi and the other in SLj for some i = j. Here we can use the hierarchy theorem to show that, supposing i < j, the SLi language is also in SLj . Then the adapted construction will establish that their intersection is in SL .

For non-closure under union (and consequently under complement) we can use the same counterexample as we did in the SL2 case:

1844_Operations on Strictly Local Languages.png

To see that this is not in SLk for any k we can use the pair

1771_Operations on Strictly Local Languages1.png

which will yield abk-1 a under k-local suffix substitution closure.

2435_Operations on Strictly Local Languages2.png

For non-closure under concatenation we can use the counterexample

The two languages being concatenated are in SL2, hence in SLk for all k ≥ 2 but their concatenation is not in SLk for any k, as we showed in the example above.


Related Discussions:- Operations on strictly local languages

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

Overview of dfa, Explain Theory of Computation ,Overview of DFA,NFA, CFG, P...

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

Problem solving and programming concepts, The Last Stop Boutique is having ...

The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

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

Describe the algorithm and draw the transition diagram, 1. Simulate a TM wi...

1. Simulate a TM with infinite tape on both ends using a two-track TM with finite storage 2. Prove the following language is non-Turing recognizable using the diagnolization

TRANSPORTATION, DEGENERATE OF THE INITIAL SOLUTION

DEGENERATE OF THE INITIAL SOLUTION

Local and recognizable languages, We developed the idea of FSA by generaliz...

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

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