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
Can v find the given number is palindrome or not using turing machine


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

LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

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

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

How useful is production function in production planning?

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

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

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