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

Strictly local languages, While the SL 2 languages include some surprising...

While the SL 2 languages include some surprisingly complex languages, the strictly 2-local automata are, nevertheless, quite limited. In a strong sense, they are almost memoryless

Qbasic, Ask question #Minimum 100 words accepte

Ask question #Minimum 100 words accepte

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

Exhaustive search, A problem is said to be unsolvable if no algorithm can s...

A problem is said to be unsolvable if no algorithm can solve it. The problem is said to be undecidable if it is a decision problem and no algorithm can decide it. It should be note

Discrete math, Find the Regular Grammar for the following Regular Expressio...

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

Can you help me in automata questions, i have some questions in automata, c...

i have some questions in automata, can you please help me in solving in these questions?

Third model of computation, Computer has a single LIFO stack containing ?xe...

Computer has a single LIFO stack containing ?xed precision unsigned integers (so each integer is subject to over?ow problems) but which has unbounded depth (so the stack itself nev

Automata, how to prove he extended transition function is derived from part...

how to prove he extended transition function is derived from part 2 and 3

Finite languages and strictly local languages, Theorem The class of ?nite l...

Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

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