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

Generalization of the interpretation of local automata, The generalization ... The generalization of the interpretation of strictly local automata as generators is similar, in some respects, to the generalization of Myhill graphs. Again, the set of possible s

Turing machine, turing machine turing machine

Context free languages, how to find whether the language is cfl or not? how to find whether the language is cfl or not?

Non - sl languages, Application of the general suffix substitution closure ... Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had

Arden''s theorem,

Positiveness problem - decision problems, For example, the question of whet... For example, the question of whether a given regular language is positive (does not include the empty string) is algorithmically decidable. "Positiveness Problem". Note that

Problem solving and programming concepts, The Last Stop Boutique is having ... The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

Instantaneous description - recognizable language, De?nition (Instantaneous... De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

Tuning machine, design a tuning machine for penidrome design a tuning machine for penidrome

Bonds, . On July 1, 2010, Harris Co. issued 6,000 bonds at $1,000 each. The... . 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