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

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

Turing, turing machine for prime numbers turing machine for prime numbers

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?

Nfas with e-transitions, We now add an additional degree of non-determinism... We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

ARDENS THROREM, PROPERTIES OF Ardens therom PROPERTIES OF Ardens therom

Context free languages, how to find whether the language is cfl or not? how to find whether the language is cfl or not?

Rubber, Rubber shortnote Rubber shortnote

Kleene closure, One might assume that non-closure under concatenation would... One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included

Transition and path functions, When an FSA is deterministic the set of trip... When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Non Regular, Prove that Language is non regular TRailing count={aa ba aaaa... Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode