Class of local languages is not closed under union, Theory of Computation

Assignment Help:

Both L1 and L2 are SL2. (You should verify this by thinking about what the automata look like.)

2360_Class of local languages is not closed under union.png

We claim that L1 ∪ L2 ∈ SL2. To see this, suppose, by way of contradiction, that it was SL2. Then it would satisfy Suffx Substitution Closure. But abb ∈ L1 ∪ L2, since it is in L1, and bba ∈ L1 ∪ L2, since it is in L2, and, by Suffx Substitution Closure, this implies that aba ∈ L1 ∪ L2, which is not the case. Hence, L1 ∪ L2 is not SL2.

It's important to not misunderstand the weight of this result. It does not show that every union of two SL2 languages is not SL2-after all, the union of any SL2 language with itself must, necessarily, be SL2. It is easy to come up with pairs of distinct SL2 languages which yield an SL2 union as well,

1737_Class of local languages is not closed under union1.png

What it does say is that one can't count on the union of SL2 languages being SL2. This is in contrast to the closure result for intersection, which lets us build up languages out of simpler SL2 languages using intersection with con?dence that the result will be SL2. Showing that our desired language is the union of some simple SL2 languages doesn't help us. The result may or may not be SL.


Related Discussions:- Class of local languages is not closed under union

Kleene closure, So we have that every language that can be constructed from...

So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Non - sl languages, Application of the general suffix substitution closure ...

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Instantaneous description of an fsa, De?nition Instantaneous Description of...

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

Flow charts, https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%...

https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

First model of computation, Computer has a single unbounded precision count...

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

Transition and path functions, When an FSA is deterministic the set of trip...

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Programming languages, Different types of applications and numerous program...

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

Shell script, shell script to print table in given range

shell script to print table in given range

Give a strictly 2-local automaton, Let L 3 = {a i bc j | i, j ≥ 0}. Give ...

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

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