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
what are composition and its function of gastric juice

De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

distinguish between histogram and historigram

Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif

Ask question #Minimum 100 words accepte

design an automata for strings having exactly four 1''s

We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Let ? ={0,1} design a Turing machine that accepts L={0^m 1^m 2^m } show using Id that a string from the language is accepted & if not rejected .

prove following function is turing computable? f(m)={m-2,if m>2, {1,if