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:

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.


Related Discussions:- Operations on strictly local languages

Numerical integration, what problems are tackled under numerical integratio...

what problems are tackled under numerical integration

Bonds, . On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The...

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r

CNF, S-->AAA|B A-->aA|B B-->epsilon

S-->AAA|B A-->aA|B B-->epsilon

Turing machine, Design a turing machine to compute x + y (x,y > 0) with x a...

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

Universality problem, The Universality Problem is the dual of the emptiness...

The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Give the acyclic paths through your graph, Give the Myhill graph of your au...

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

Equivalence of nfas, It is not hard to see that ε-transitions do not add to...

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd