Boolean operations - class of recognizable languages, Theory of Computation

Assignment Help:

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.


Related Discussions:- Boolean operations - class of recognizable languages

Turing machine, Can v find the given number is palindrome or not using turi...

Can v find the given number is palindrome or not using turing machine

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

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

#turing machine, #can you solve a problem of palindrome using turing machin...

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

Shell script, shell script to print table in given range

shell script to print table in given range

Find a regular expression, Find a regular expression for the regular langua...

Find a regular expression for the regular language L={w | w is decimal notation for an integer that is a multiple of 4}

Local and recognizable languages, We developed the idea of FSA by generaliz...

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

Context free grammar, A context free grammar G = (N, Σ, P, S)  is in binary...

A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Turing machine, design a turing machine that accepts the language which con...

design a turing machine that accepts the language which consists of even number of zero''s and even number of one''s?

Design and implementation of the state machine, You are required to design ...

You are required to design a system that controls the speed of a fan's rotation. The speed at which the fan rotates is determined by the ambient temperature, i.e. as the temperatur

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd