Closure properties of recognizable languages, Theory of Computation

We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also be recognizable. But what about the class of recognizable languages as a whole? Are Boolean combinations of recognizable (not just LT) languages also recognizable. In answering we can use the same methodology we use to show that any language is recognizable: consider what we need to keep track of in scanning a string in order to determine if it belongs to the language or not and then use that information to build our state set.

Suppose, then, that L = L1 ∩ L2, where L1 and L2 are both recognizable. A string w will be in L iff it is in both L1 and L2. Since they are recognizable there exist DFAs A1 and A2 for which L1 = L(A1) and L2 = L(A2). We can tell if the string is in L1 or L2 simply by keeping track of the state of the corresponding automaton. We can tell if it is in both by keeping track of both states simultaneously.

Posted Date: 3/21/2013 3:06:13 AM | Location : United States







Related Discussions:- Closure properties of recognizable languages, Assignment Help, Ask Question on Closure properties of recognizable languages, Get Answer, Expert's Help, Closure properties of recognizable languages Discussions

Write discussion on Closure properties of recognizable languages
Your posts are moderated
Related Questions
https://www.google.com/search?q=The+fomula+n%3D%28x%3D0%29%2F%281%3D2%29.The+value+x%3D0+and+is+used+to+stop+the+algerithin.The+calculation+is+reapeated+using+values+of+x%3D0+is+in

The initial ID of the automaton given in Figure 3, running on input ‘aabbba' is (A, aabbba) The ID after the ?rst three transitions of the computation is (F, bba) The p

Claim Under the assumptions above, if there is an algorithm for checking a problem then there is an algorithm for solving the problem. Before going on, you should think a bit about

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

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define part

Our DFAs are required to have exactly one edge incident from each state for each input symbol so there is a unique next state for every current state and input symbol. Thus, the ne

how to find whether the language is cfl or not?

Another way of interpreting a strictly local automaton is as a generator: a mechanism for building strings which is restricted to building all and only the automaton as an inexh

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

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