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

Two-tape turing machine, Let there L1 and L2 . We show that L1 ∩ L2 is CFG ... Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Formal language theory, This was one of the ?rst substantial theorems of Fo... This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

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

Equivalence of nfas, It is not hard to see that ε-transitions do not add to... It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ v) directly computes another (p, v) via

Transition graph for the automaton, Lemma 1 A string w ∈ Σ* is accepted by ... 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

Automata, how to prove he extended transition function is derived from part... how to prove he extended transition function is derived from part 2 and 3

Automata and compiler, Automata and Compiler (1) [25 marks] Let N be the... Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Pendulum Swings, how many pendulum swings will it take to walk across the c... how many pendulum swings will it take to walk across the classroom?

Operator p, implementation of operator precedence grammer implementation of operator precedence grammer

Can you help me in automata questions, i have some questions in automata, c... i have some questions in automata, can you please help me in solving in these questions?