Class of recognizable languages, Theory of Computation

Proof (sketch): Suppose L1 and L2 are recognizable. Then there are DFAs A1 = (Q,Σ, T1, q0, F1) and A2 = (P,Σ, T2, p0, F2) such that L1 = L(A1) and L2 = L(A2). We construct A′ such that L(A′ ) = L1 ∩ L2. The idea is to have A′ run A1 and A2 in parallel-keeping track of the state of both machines. It will accept a string, then, iff both machines reach an accepting state on that string.

Let A′ = (Q × P,Σ, T′ , (q0, p0), F1 × F2), where

T′ def= [{((q, pi, (q′, p′), σ) | (q, q′, σi)∈ T1 and (p, p′, σ ∈ T2}.

2294_Class of recognizable languages.png

Then

(You should prove this; it is an easy induction on the structure of w.) It follows then that

751_Class of recognizable languages1.png

Posted Date: 3/21/2013 3:13:26 AM | Location : United States







Related Discussions:- Class of recognizable languages, Assignment Help, Ask Question on Class of recognizable languages, Get Answer, Expert's Help, Class of recognizable languages Discussions

Write discussion on Class of recognizable languages
Your posts are moderated
Related Questions
The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea

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 .

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Ask question #Minimum 100 words accepte

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


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

Describe the architecture of interface agency

how to convert a grammar into GNF

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