Both L₁ and L₂ are SL₂. (You should verify this by thinking about what the automata look like.)

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

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,

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.

Posted Date: 3/22/2013 12:53:40 AM | Location : United States

Ask an Expert

Related Discussions:- Class of local languages is not closed under union, Assignment Help, Ask Question on Class of local languages is not closed under union, Get Answer, Expert's Help, Class of local languages is not closed under union Discussions

Write discussion on Class of local languages is not closed under union
Your posts are moderated

Write your message here..

Related Questions

Path function of a nfa, The path function δ : Q × Σ* → P(Q) is the extensio... The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

Pushdown automator, draw pda for l={an,bm,an/m,n>=0} n is in superscript draw pda for l={an,bm,an/m,n>=0} n is in superscript

Finiteness of languages is decidable, To see this, note that if there are a... To see this, note that if there are any cycles in the Myhill graph of A then L(A) will be infinite, since any such cycle can be repeated arbitrarily many times. Conversely, if the

Prove the arden''s theorem, State and Prove the Arden's theorem for Regular... State and Prove the Arden's theorem for Regular Expression

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

Theory of computation, Computations are deliberate for processing informati... Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

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

Gephi, construct a social network from the real-world data, perform some si... construct a social network from the real-world data, perform some simple network analyses using Gephi, and interpret the results.

Design and implementation of the state machine, You are required to design ... You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

Strictly k-local automata, Strictly 2-local automata are based on lookup ta... Strictly 2-local automata are based on lookup tables that are sets of 2-factors, the pairs of adjacent symbols which are permitted to occur in a word. To generalize, we extend the