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
#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

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

For every regular language there is a constant n depending only on L such that, for all strings x ∈ L if |x| ≥ n then there are strings u, v and w such that 1. x = uvw, 2. |u

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

how many pendulum swings will it take to walk across the classroom?

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

Prove that Language is non regular TRailing count={aa ba aaaa abaa baaa bbaa aaaaaa aabaaa abaaaa..... 1) Pumping Lemma 2)Myhill nerode