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

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

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

Computations of sl automata, We will specify a computation of one of these ... We will specify a computation of one of these automata by specifying the pair of the symbols that are in the window and the remainder of the string to the right of the window at ea

what is a turing machine, A Turing machine is a theoretical computing mach... A Turing machine is a theoretical computing machine made-up by Alan Turing (1937) to serve as an idealized model for mathematical calculation. A Turing machine having of a line of

Recognition problem, The Recognition Problem for a class of languages is th... The Recognition Problem for a class of languages is the question of whether a given string is a member of a given language. An instance consists of a string and a (?nite) speci?cat

Find regular grammar : a(a+b)*(ab*+ba*)b, Find the Regular Grammar for the ... Find the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

Complement - operations on languages, The fact that SL 2 is closed under i... The fact that SL 2 is closed under intersection but not under union implies that it is not closed under complement since, by DeMorgan's Theorem L 1 ∩ L 2 = We know that

Ogdens lemma, proof ogdens lemma .with example i am not able to undestand ... proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

Nfas with e-transitions, We now add an additional degree of non-determinism... We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

Toc, how to understand DFA ? how to understand DFA ?