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 SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

. On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The bonds paid interest semiannually at 5%. The bonds had a term of 20 years. At the time of issuance, the market r

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

s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

It is not hard to see that ε-transitions do not add to the accepting power of the model. The underlying idea is that whenever an ID (q, σ  v) directly computes another (p, v) via

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan


The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular