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

Complement - operations on languages, The fact that SL 2 is closed under i...

The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

Normal forms, how to convert a grammar into GNF

how to convert a grammar into GNF

Alphabets - strings and representation, A finite, nonempty ordered set will...

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

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?

Agents architecture, Describe the architecture of interface agency

Describe the architecture of interface agency

Algorithm for the universal recognition problem, Sketch an algorithm for th...

Sketch an algorithm for the universal recognition problem for SL 2 . This takes an automaton and a string and returns TRUE if the string is accepted by the automaton, FALSE otherwi

Decision problems, In Exercise 9 you showed that the recognition problem an...

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Prism algorithm, what exactly is this and how is it implemented and how to ...

what exactly is this and how is it implemented and how to prove its correctness, completeness...

Non-determinism - recognizable language, Our DFAs are required to have exac...

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

Chomsky-schutzenberger, The upper string r ∈ Q+ is the sequence of states v...

The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

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