Cheap and Secure Web Hosting Provider : See Now

[Solved]: Null Characters and Splitting the String in the Pumping Lemma

, , No Comments
Problem Detail: 

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take the problem prove that $L = \{w | w$ contains more $0$'s than $1$'s over the language $\{0,1\} \}$ is not regular via the pumping lemma.

So I choose the string $01^{p}0^{p}$. Since this is a regular language pumping lemma problem I know that:

  1. for each $i > 0, xy^{i}z \in A$,
  2. $|y^{i}| > 0$, and
  3. $|xy| < p$

I am little uncertain about other possibilites though, such as if $x$, or $z$ can be null (obviously $y$ can't by condition 2). I assume that this isn't possible since I don't think the preceding or trailing whitespace is considered part of the string, but I'm not sure. Is it possible for $x$ or $z$ to be null?

Asked By : BrotherJack

Answered By : Dave Clarke

Yes, it is possible for $x$ or $z$ to be 'null', if by 'null' you mean the empty string. The empty string, $\epsilon$, is the string of length zero.

If the loop in the automaton (which is ultimately what the pumping lemma refers to) starts at the initial state and the initial state is also an accepting state, then strings of the form $y^i$ will be accepted, where $y$ is some string that will take you around the loop.

Whitespace plays no role in this theorem. Formal languages are defined over a given alphabet, in your case $\{0,1\}$. This is the only alphabet relevant for the question. There is no preceding or trailing whitespace when talking about the pumping lemma. Spaces, tabs, return characters play absolutely no role.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1469

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback