Kleene closure, Theory of Computation

Assignment Help:

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.


Related Discussions:- Kleene closure

Mealy machine, Construct a Mealy machine that can output EVEN or ODD Accord...

Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1''s encountered is even or odd.

Notes, write short notes on decidable and solvable problem

write short notes on decidable and solvable problem

Powerset construction, As de?ned the powerset construction builds a DFA wit...

As de?ned the powerset construction builds a DFA with many states that can never be reached from Q′ 0 . Since they cannot be reached from Q′ 0 there is no path from Q′ 0 to a sta

First model of computation, Computer has a single unbounded precision count...

Computer has a single unbounded precision counter which you can only increment, decrement and test for zero. (You may assume that it is initially zero or you may include an explici

Distinguish between mealy and moore machine, Distinguish between Mealy and ...

Distinguish between Mealy and Moore Machine? Construct a Mealy machine that can output EVEN or ODD According to the total no. of 1's encountered is even or odd.

Union, Intuitively, closure of SL 2 under intersection is reasonably easy ...

Intuitively, closure of SL 2 under intersection is reasonably easy to see, particularly if one considers the Myhill graphs of the automata. Any path through both graphs will be a

#turing machine, #can you solve a problem of palindrome using turing machin...

#can you solve a problem of palindrome using turing machine with explanation and diagrams?

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?

Xx, Ask queyystion #Minimum 100 words accepted#

Ask queyystion #Minimum 100 words accepted#

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