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

M=

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
First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

We will assume that the string has been augmented by marking the beginning and the end with the symbols ‘?' and ‘?' respectively and that these symbols do not occur in the input al

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

shell script to print table in given range

If the first three words are the boys down,what are the last three words??

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

#Your company has 25 licenses for a computer program, but you discover that it has been copied onto 80 computers. You informed your supervisor, but he/she is not willing to take an

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

c program to convert dfa to re

When we say "solved algorithmically" we are not asking about a speci?c programming language, in fact one of the theorems in computability is that essentially all reasonable program