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

Designing finite automata, a finite automata accepting strings over {a,b} e...

a finite automata accepting strings over {a,b} ending in abbbba

# Help, #Your company has 25 licenses for a computer program, but you disco...

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

Positiveness problem - decision problems, For example, the question of whet...

For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Toc, how to understand DFA ?

how to understand DFA ?

Applying the pumping lemma, Applying the pumping lemma is not fundamentally...

Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors...

The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

Myhill-nerode, Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff...

Theorem (Myhill-Nerode) A language L ⊆ Σ is recognizable iff ≡L partitions Σ* into ?nitely many Nerode equivalence classes. Proof: For the "only if" direction (that every 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