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

Constract Context free, constract context free g ={ a^n b^m : m,n >=0 and n... constract context free g ={ a^n b^m : m,n >=0 and n

Non - sl languages, The key thing about the Suffx Substitution Closure prop... The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ... Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

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

Wearable computers.., what are the advantages and disadvantages of wearable... what are the advantages and disadvantages of wearable computers?

Arden''s theoram, proof of arden''s theoram proof of arden''s theoram

Qbasic, Ask question #Minimum 100 words accepte Ask question #Minimum 100 words accepte

Flow charts, https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%... https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ... Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Abstract model of computation, When we say "solved algorithmically" we are ... When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program