سؤال

I am trying to show how the pumping lemma applies to a language that is for sure regular. I have the language over {0, 1} that has an even number of 1's. This language can be represented by a DFA that has two states.

So the pumping length here is 2, correct? The pumping lemma states that "if s is any string in A of length at least p," then it may be divided into xyz such that the 3 PL conditions are true. So say we choose a string '000110' and want to show that somehow it can be split into xyz such that |xy| <= p (and |y| > 0, and x(y^i)z is in L).

In this case y would have to be '11' so that it can be repeated and still be even... which would make x = '000', right? This would then make |xy| = 5, which is more than p.

I don't see any other way of splitting the given string so that |xy| < p. What am I missing here? Thanks very much.

هل كانت مفيدة؟

المحلول

@Jim Lewis provided the answer to my question - we can have x = empty string, y = '0' and a z of '00110', which will enabled us to pump y as much (or as little) as we want, satisfying the requirements of the pumping lemma. Thanks!

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top