Union, Theory of Computation

Intuitively, closure of SL2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a path through the intersection of the graphs (by which we mean the graph resulting by taking the intersection of the vertex sets and the intersection of the edge sets).

For the union, on the other hand, the corresponding construction won't work. An automaton built from the union of the two automata will still recognize all of the strings in L1 and all of the strings in L2, but it is likely to also recognize strings made up of adjacent pairs from L1 combined with adjacent pairs from L2 that aren't in either language. And, in fact, we can use Suffx Substitution Closure to show that there are languages that are the union of two SL2 languages that are not, themselves, SL2.

Posted Date: 3/22/2013 12:49:44 AM | Location : United States







Related Discussions:- Union, Assignment Help, Ask Question on Union, Get Answer, Expert's Help, Union Discussions

Write discussion on Union
Your posts are moderated
Related Questions
Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

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


c program to convert dfa to re

The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

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

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

Lemma 1 A string w ∈ Σ* is accepted by an LTk automaton iff w is the concatenation of the symbols labeling the edges of a path through the LTk transition graph of A from h?, ∅i to

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

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