Boolean operations - class of recognizable languages, Theory of Computation

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 ∈ F1 or p ∈ F2}. Then L(A′ ) = L1 ∪ L2.

• Relative complement: Let F′ = F1 × (Q2 - F2). Then L(A′ ) = L1 -L2.

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

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







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
Related Questions
State and Prove the Arden's theorem for Regular Expression

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

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

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

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 the Regular Grammar for the following Regular Expression:                    a(a+b)*(ab*+ba*)b.

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

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

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

how to understand DFA ?