Kleene closure, Theory of Computation

One might assume that non-closure under concatenation would imply non closure under both Kleene- and positive closure, since the concatenation of a language with itself is included in its positive closure (that is, L2 ⊆ L+). The intuitive idea is that if we had a counterexample for closure under concatenation that uses just a single language L, then if there was some pair of strings in L2 that invalidates suffx substitution closure-that yields a string not in L2 when the suffx of one is substituted into the other-then that pair would invalidate suffx substitution closure for L* as well. But this argument doesn't work. The fact that the pair yields a string that is not in L2 does not rule out the possibility of string being in Li for some i = 2.

If one thinks in terms of strictly local generation, it should be clear that a language L is strictly 2-local language i? it includes all and only the strings that start with a symbol from some particular subset of Σ and end with a symbol from another such subset, with only  particular pairs of adjacent symbols occurring in between-equivalently, some particular set of forbidden pairs not occurring (see Section 3 of Part 1).

Consider, then L+. Strings in L+ will also start and end with symbols from those subsets of Σ and the adjacent pairs of symbols occurring strictly within the string from a given iteration of L will be only those that are permitted. The only di?erence is that there may be additional adjacent pairs where the strings from successive iterations meet. These we can admit by simply permitting them as well. The question is whether they will allow pairs in the middle of a string from L which should be forbidden. But, since we are only adding pairs in which the left symbol is a permissible ending symbol for a string from L and the right symbol is a permissible starting symbol, everywhere such a pair occurs is a permissible boundary between strings of L. Finally, to extend the construction to get L* all we need to do is add the pair ?? as well.

Posted Date: 3/22/2013 1:01:57 AM | Location : United States







Related Discussions:- Kleene closure, Assignment Help, Ask Question on Kleene closure, Get Answer, Expert's Help, Kleene closure Discussions

Write discussion on Kleene closure
Your posts are moderated
Related Questions
The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?}Σ and some factors in Σ{?} distinguishing symbols that may occur at the beginning and en

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

This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

We developed the idea of FSA by generalizing LTk transition graphs. Not surprisingly, then, every LTk transition graph is also the transition graph of a FSA (in fact a DFA)-the one

The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

Give the Myhill graph of your automaton. (You may use a single node to represent the entire set of symbols of the English alphabet, another to represent the entire set of decima

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

First model: Computer has a ?xed number of bits of storage. You will model this by limiting your program to a single ?xed-precision unsigned integer variable, e.g., a single one-by

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

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