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
Applying the pumping lemma is not fundamentally di?erent than applying (general) su?x substitution closure or the non-counting property. The pumping lemma is a little more complica

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

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

Suppose G = (N, Σ, P, S) is a reduced grammar (we can certainly reduce G if we haven't already). Our algorithm is as follows: 1. Define maxrhs(G) to be the maximum length of the


These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third


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

We can then specify any language in the class of languages by specifying a particular automaton in the class of automata. We do that by specifying values for the parameters of the

The fact that the Recognition Problem is decidable gives us another algorithm for deciding Emptiness. The pumping lemma tells us that if every string x ∈ L(A) which has length grea