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

Construct a recognizer, Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG t...

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too. 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 sec

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ...

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

#turing machine, #can you solve a problem of palindrome using turing machin...

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

REGULAR GRAMMAR, Find the Regular Grammar for the following Regular Express...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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}

Class of local languages is not closed under union, Both L 1 and L 2 are ...

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con

Prepare the consolidated financial statements, Prepare the consolidated fin...

Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J

Non-regular languages, Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = ...

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

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