Operations on strictly local languages, Theory of Computation

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.

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







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
Related Questions
Differentiate between DFA and NFA. Convert the following Regular Expression into DFA. (0+1)*(01*+10*)*(0+1)*. Also write a regular grammar for this DFA.

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

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

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

And what this money. Invovle who it involves and the fact of,how we got itself identified candidate and not withstanding time date location. That shouts me media And answers who''v


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

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless