Pumping lemma constant, Theory of Computation

a) Let n be the pumping lemma constant. Then if L is regular, PL implies that s can be decomposed into xyz, |y| > 0, |xy| ≤n, such that xy i z is in L for all i ≥0.

Since the length of xy ≤n, y consists of all b's Then xy 2 z = anbncn, where the length of of y = j. We know j > 0 so the length of the pumped string contains at as many a's as b's as c's, and is not in L. This is a Contradiction L = {w :| n a (w) = n b (w) = nc(w)}

b)

  • Let n be the pumping lemma constant. Then if L is regular, PL implies that s = anbncm can be decomposed into xyz, |y| > 0, |xy| ≤n, such thatxy i z is in L for all i ≥0.
  • Since the length of xy ≤n, there are three ways to partition s:

1. y consists of all a's

Pumping y will lead to a string with more than n a's -- not in L

2. y consists of all b's

Pumping y will lead to a string with more than m b's, and leave

the number of c's untouched, such that there are no longer 2n more c's than b's -- not in L

3. y consists of a's and b's

Pumping y will lead to a string with b's before a's, -- not in L

  • There is no way to partition anbncm that pumped strings are still in L.
Posted Date: 2/23/2013 12:53:05 AM | Location : United States







Related Discussions:- Pumping lemma constant, Assignment Help, Ask Question on Pumping lemma constant, Get Answer, Expert's Help, Pumping lemma constant Discussions

Write discussion on Pumping lemma constant
Your posts are moderated
Related Questions
All that distinguishes the de?nition of the class of Regular languages from that of the class of Star-Free languages is that the former is closed under Kleene closure while the lat

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

Exercise Show, using Suffix Substitution Closure, that L 3 . L 3 ∈ SL 2 . Explain how it can be the case that L 3 . L 3 ∈ SL 2 , while L 3 . L 3 ⊆ L + 3 and L + 3 ∈ SL

Kleene called this the Synthesis theorem because his (and your) proof gives an effective procedure for synthesizing an automaton that recognizes the language denoted by any given r

how many pendulum swings will it take to walk across the classroom?

prove following function is turing computable? f(m)={m-2,if m>2, {1,if

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting


The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages. Lemma (k-Local Suffix Substitution Clo

Application of the general suffix substitution closure theorem is slightly more complicated than application of the specific k-local versions. In the specific versions, all we had