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
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

Let there L1 and L2 . We show that L1 ∩ L2 is CFG . Let M1 be a decider for L1 and M2 be a decider for L2 . Consider a 2-tape TM M: "On input x: 1. copy x on the second

Let L 3 = {a i bc j | i, j ≥ 0}. Give a strictly 2-local automaton that recognizes L 3 . Use the construction of the proof to extend the automaton to one that recognizes L 3 . Gi

Normal forms are important because they give us a 'standard' way of rewriting and allow us to compare two apparently different grammars G1  and G2. The two grammars can be shown to

how to convert a grammar into GNF

Both L 1 and L 2 are SL 2 . (You should verify this by thinking about what the automata look like.) We claim that L 1 ∪ L 2 ∈ SL 2 . To see this, suppose, by way of con


Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

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