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, Design a turing machine to compute x + y (x,y > 0) with x a...

Design a turing machine to compute x + y (x,y > 0) with x an y in unary, seperated by a # (descrition and genereal idea is needed ... no need for all TM moves)

Class of recognizable languages, Proof (sketch): Suppose L 1 and L 2 are ...

Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(

#title., distinguish between histogram and historigram

distinguish between histogram and historigram

Wearable computers.., what are the advantages and disadvantages of wearable...

what are the advantages and disadvantages of wearable computers?

Non - sl languages, The key thing about the Suffx Substitution Closure prop...

The key thing about the Suffx Substitution Closure property is that it does not make any explicit reference to the automaton that recognizes the language. While the argument tha

How to solve the checking problem, The objective of the remainder of this a...

The objective of the remainder of this assignment is to get you thinking about the problem of recognizing strings given various restrictions to your model of computation. We will w

Mapping reducibility, (c) Can you say that B is decidable? (d) If you someh...

(c) Can you say that B is decidable? (d) If you somehow know that A is decidable, what can you say about B?

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