Construct a recognizer, Theory of Computation

Let L1 and L2 be CGF. We show that L1 ∩ L2 is CFG too.

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 tape

2. on the ?rst tape run M1 on x


3. if M1 accepted then goto 4. else M rejects

4. on the second tape run M2 on x

5. if M2 accepted then M accepts else M rejects."

The machine M is a decider and it accepts a string x i? both M1 and M2 accept x.

Two-tape TM is as expressive as the single tape TM.


8.3 b)

Let L1 and L2 be recognizable languages with the corresponding recognizers M1 and M2 . We construct a recognizer M for L1 ∪ L2 .

Strategy I: run M1 and M2 in parallel on a 2-tape TM M

M = "On input x:

1. Copy x on the second tape.

2. Do one step of M1 on tape 1 and one step of M2 on tape 2.

3. If either M1 or M2 accepted, then M accepts, else goto 2."

Strategy II: nondeterministically choose to run M1 or M2

M = "On input x:

1. Nondeterministically choose i ∈ {1, 2}.

2. Run machine Mi on the input x.

3. If Mi accepted, then M accepts.

If Mi rejected, then M rejects."

Posted Date: 2/23/2013 12:52:16 AM | Location : United States

Related Discussions:- Construct a recognizer, Assignment Help, Ask Question on Construct a recognizer, Get Answer, Expert's Help, Construct a recognizer Discussions

Write discussion on Construct a recognizer
Your posts are moderated
Related Questions

S-->AAA|B A-->aA|B B-->epsilon

Theorem The class of recognizable languages is closed under Boolean operations. The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a give

Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

Give DFA''s accepting the following languages over the alphabet {0,1}: i. The set of all strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5.

matlab v matlab

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

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

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.