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


(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 Emptiness Problem is the problem of deciding if a given regular language is empty (= ∅). Theorem 4 (Emptiness) The Emptiness Problem for Regular Languages is decidable. P

examples of decidable problems

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

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

De?nition Instantaneous Description of an FSA: An instantaneous description (ID) of a FSA A = (Q,Σ, T, q 0 , F) is a pair (q,w) ∈ Q×Σ* , where q the current state and w is the p

In Exercise 9 you showed that the recognition problem and universal recognition problem for SL2 are decidable. We can use the structure of Myhill graphs to show that other problems

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

build a TM that enumerate even set of even length string over a

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular