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

Arden''s theoram, proof of arden''s theoram proof of arden''s theoram

Vogel Approximation Method(VAM, how to write program Minimum Cost Calculat... how to write program Minimum Cost Calculation - Vogel Approximation Method(VAM

Chomsky normal form, s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbo... s->0A0|1B1|BB A->C B->S|A C->S|null find useless symbol?

Powerset construction, As de?ned the powerset construction builds a DFA wit... 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

9765432165, jhfsaadsa jhfsaadsa

Computation and languages, When we study computability we are studying prob... When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

Decision Theroy, spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8... spam messages h= 98%, m= 90%, l= 80% non spam h=12%, m = 8%, l= 5% The organization estimates that 75% of all messages it receives are spam messages. If the cost of not blocking a

Brain game, If the first three words are the boys down,what are the last th... If the first three words are the boys down,what are the last three words??

Finite-state automaton, Paths leading to regions B, C and E are paths which... Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

Strictly 2 - local automata, We will assume that the string has been augmen... 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