Concatenation, Theory of Computation

We saw earlier that LT is not closed under concatenation. If we think in terms of the LT graphs, recognizing the concatenation of LT languages would seem to require knowing, while scanning a string in L1 . L2, for instance, when to switch from keeping track of factors for L1 to keeping track of factors from L2.

Assuming that the alphabets were not disjoint, there is (evidently, since LT is not closed under concatenation) no way, in general, to know that. For the recognizable languages, on the other hand, we have the convenience of being able to work with non-determinism. We don't actually have to know when to switch from one automaton to the next. Whenever we get to a point in the string that could possibly be the end of the pre?x that is in L1 we can just allow for a non-deterministic choice of whether to continue scanning for A1 (the machine recognizing L1) or to switch to scanning for A2. Since whenever the string is in L1 .  L2 there will be some correct place to switch and since acceptance by a NFA requires only that there some accepting computation, the combined automaton will accept every string in L1 . L2. Moreover, the combined automaton will accept a string iff there is some point at which it can be split into a string accepted by A1 followed by one accepted by A2: it accepts all and only the strings in L1 . L2.

Posted Date: 3/21/2013 3:18:22 AM | Location : United States







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

Write discussion on Concatenation
Your posts are moderated
Related Questions
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

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

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

how to understand DFA ?

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

The fact that regular languages are closed under Boolean operations simpli?es the process of establishing regularity of languages; in essence we can augment the regular operations

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

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

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