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

#dfa, Give DFA''s accepting the following languages over the alphabet {0,1}...

Give DFA''s accepting the following languages over the alphabet {0,1}: i. The set of all strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5.

Formal language theory, This was one of the ?rst substantial theorems of Fo...

This was one of the ?rst substantial theorems of Formal Language Theory. It's maybe not too surprising to us, as we have already seen a similar equivalence between LTO and SF. But

Pushdown automator, draw pda for l={an,bm,an/m,n>=0} n is in superscript

draw pda for l={an,bm,an/m,n>=0} n is in superscript

Pendulum Swings, how many pendulum swings will it take to walk across the c...

how many pendulum swings will it take to walk across the classroom?

What is pumping lemma for regular sets, State & prove pumping lemma for reg...

State & prove pumping lemma for regular set. Show that for the language L={ap |p is a prime} is not regular

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

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)

Prism algorithm, what exactly is this and how is it implemented and how to ...

what exactly is this and how is it implemented and how to prove its correctness, completeness...

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