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
construct a social network from the real-world data, perform some simple network analyses using Gephi, and interpret the results.

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

Ask question #hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhMinimum 100 words accepted#

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

matlab v matlab


#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

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

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

The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p