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

What is theory of computtion, what is theory of computtion what is theory of computtion

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

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?

Finite automata, design an automata for strings having exactly four 1''s design an automata for strings having exactly four 1''s

Project, can you plz help with some project ideas relatede to DFA or NFA or... can you plz help with some project ideas relatede to DFA or NFA or anything

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

Powerset construction, As de?ned the powerset construction builds a DFA wit... As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

Mapping reducibility, Can you say that B is decidable? If you somehow know... Can you say that B is decidable? If you somehow know that A is decidable, what can you say about B?

Operations on strictly local languages, The class of Strictly Local Languag... The class of Strictly Local Languages (in general) is closed under • intersection but is not closed under • union • complement • concatenation • Kleene- and positive

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