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
write grammer to produce all mathematical expressions in c.

what problems are tackled under numerical integration

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 le

Proof (sketch): Suppose L 1 and L 2 are recognizable. Then there are DFAs A 1 = (Q,Σ, T 1 , q 0 , F 1 ) and A 2 = (P,Σ, T 2 , p 0 , F 2 ) such that L 1 = L(A 1 ) and L 2 = L(


The path function δ : Q × Σ* → P(Q) is the extension of δ to strings: This just says that the path labeled ε from any given state q goes only to q itself (or rather never l

The computation of an SL 2 automaton A = ( Σ, T) on a string w is the maximal sequence of IDs in which each sequential pair of IDs is related by |- A and which starts with the in

A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

1. An integer is said to be a “continuous factored” if it can be expresses as a product of two or more continuous integers greater than 1. Example of continuous factored integers

examples of decidable problems