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

Myhill-nerode theorem, The Myhill-Nerode Theorem provided us with an algori... The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

Ardens theorem, how is it important how is it important

Abstract model for an algorithm solving a problem, These assumptions hold f... These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third

Multiple instruction single data stream, short application for MISD short application for MISD

Language accepted by a nfa, The language accepted by a NFA A = (Q,Σ, δ, q 0... The language accepted by a NFA A = (Q,Σ, δ, q 0 , F) is NFAs correspond to a kind of parallelism in the automata. We can think of the same basic model of automaton: an inpu

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

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

Strictly local generation automaton, Another way of interpreting a strictly... Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

NP complete, I want a proof for any NP complete problem I want a proof for any NP complete problem

Regular languages, LTO was the closure of LT under concatenation and Boolea... LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl