## Operations on strictly local languages, Theory of Computation

Assignment Help:

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:

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.

#### Parallel computing, Perfect shuffle permutation

Perfect shuffle permutation

#### Regular expression, what is regular expression?

what is regular expression?

#### Toc, how to understand DFA ?

how to understand DFA ?

#### 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

#### Find a regular expression, Find a regular expression for the regular langua...

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

#### What is theory of computtion, what is theory of computtion

what is theory of computtion

#### 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

#### Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ...

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

#### Data retriving, i have research method project and i meef to make prposal w...

i have research method project and i meef to make prposal with topic. If this service here please help me

#### Computer achitecture, what is a bus and draw a single bus structure

what is a bus and draw a single bus structure