Theorem The class of recognizable languages is closed under Boolean operations.

The construction of the proof of Lemma 3 gives us a DFA that keeps track of whether or not a given string is in either or both of any pair of recognizable languages. We can modify the construction for other Boolean operations simply by selecting the appropriate set of accepting states:

• Union: Let F′

= {(q, p) | q ∈ F₁ or p ∈ F₂}. Then L(A′ ) = L₁ ∪ L₂.

• Relative complement: Let F′ = F1 × (Q₂ - F₂). Then L(A′ ) = L₁ -L₂.

• Complement: Let L1 = Σ* and use the construction for relative complement.

Posted Date: 3/21/2013 3:15:49 AM | Location : United States

Ask an Expert

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

Write discussion on Boolean operations - class of recognizable languages
Your posts are moderated

Write your message here..

Related Questions

Non-regular languages, Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = ... Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

Kleene closure, So we have that every language that can be constructed from... So we have that every language that can be constructed from SL languages using Boolean operations and concatenation (that is, every language in LTO) is recognizable but there are r

Qbasic, Ask question #Minimum 100 words accepte Ask question #Minimum 100 words accepte

Theorey Of Computation, program in C++ of Arden''s Theorem program in C++ of Arden''s Theorem

Prove the arden''s theorem, State and Prove the Arden's theorem for Regular... State and Prove the Arden's theorem for Regular Expression

Equivalence problem, The Equivalence Problem is the question of whether two... 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

Pojects idea, i want to do projects for theory of computation subject what ... i want to do projects for theory of computation subject what topics should be best.

Computer architecture, What are the issues in computer design? What are the issues in computer design?

Define ambiguity in cfg, Define the following concept with an example: a.  ... Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

Prepare the consolidated financial statements, Prepare the consolidated fin... Prepare the consolidated financial statements for the year ended 30 June 2011. On 1 July 2006, Mark Ltd acquired all the share capitall of john Ltd for $700,000. At the date , J