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 SL₂ 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 SL₂ case:

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

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

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.

Posted Date: 3/22/2013 2:05:18 AM | Location : United States

Ask an Expert

Related Discussions:- Operations on strictly local languages, Assignment Help, Ask Question on Operations on strictly local languages, Get Answer, Expert's Help, Operations on strictly local languages Discussions

Write discussion on Operations on strictly local languages
Your posts are moderated

Write your message here..

Related Questions

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.

Agents architecture, Describe the architecture of interface agency Describe the architecture of interface agency

Shell script, shell script to print table in given range shell script to print table in given range

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.

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors... The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?} Σ and some factors in Σ {?} distinguishing symbols that may occur at the beginning and en

Algorithm, What is the Best way to write algorithm and construct flow chart... What is the Best way to write algorithm and construct flow chart? What is Computer? How to construct web page and Designe it?

What is pumping lemma for regular sets, State & prove pumping lemma for reg... State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

#title., distinguish between histogram and historigram distinguish between histogram and historigram

Production, How useful is production function in production planning? How useful is production function in production planning?

Boolean operations - class of recognizable languages, Theorem The class of ... Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give