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 L₁ .
L₂, for instance, when to switch from keeping track of factors for L₁ to keeping track of factors from L₂.

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 L₁ we can just allow for a non-deterministic choice of whether to continue scanning for A₁ (the machine recognizing L₁) or to switch to scanning for A₂. Since whenever the string is in L₁ .
L₂ 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 L₁ .
L₂. 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 L₁
. L₂.

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

Ask an Expert

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

Write discussion on Concatenation
Your posts are moderated

Write your message here..

Related Questions

First model of computation, Computer has a single unbounded precision count... 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

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

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

Toc, how to understand DFA ? how to understand DFA ?

Local suffix substitution closure, The k-local Myhill graphs provide an eas... 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 ambiguity in cfg, Define the following concept with an example: a.  ... Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

Closure properties to prove regularity, The fact that regular languages are... 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

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

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

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