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
A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

c program to convert dfa to re

When an FSA is deterministic the set of triples encoding its edges represents a relation that is functional in its ?rst and third components: for every q and σ there is exactly one

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

design an automata for strings having exactly four 1''s

can you plz help with some project ideas relatede to DFA or NFA or anything

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

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

What are the benefits of using work breakdown structure, Project Management

As we are primarily concerned with questions of what is and what is not computable relative to some particular model of computation, we will usually base our explorations of langua