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 2-local languages, The fundamental idea of strictly local language...

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

#title., distinguish between histogram and historigram

distinguish between histogram and historigram

Decidability, examples of decidable problems

examples of decidable problems

Path function of a nfa, The path function δ : Q × Σ* → P(Q) is the extensio...

The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

Theory of computation, Computations are deliberate for processing informati...

Computations are deliberate for processing information. Computability theory was discovered in the 1930s, and extended in the 1950s and 1960s. Its basic ideas have become part of

Automata, automata of atm machine

automata of atm machine

Computations of sl automata, We will specify a computation of one of these ...

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

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

DFA, designing DFA

designing DFA

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