2
$\begingroup$

I checked the pumping lemma in many books(introduction to the theory of computation Michael Sipser) and website(wikipedia). they all give the same explanation:(definition from introduction to the theory of computation, page 78)

Pumping lemma: If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  1. for each $i \ge 0$, $xy^iz \in A$,
  2. $|y| > 0$, and
  3. $|xy| \le p$.

I want to know, is it possible to choose a fractional value such as $\frac{1}{3}$ for $i$?? if it is possible, how to you interpret it??

$\endgroup$
3
$\begingroup$

No. In automata theory unless indicated otherwise all the values being dealt with are natural numbers. The $i$ indicates the length of repeated $y$ substrings and as it is a finite cardinality only natural numbers makes sense.

$\endgroup$
0
$\begingroup$

As a counterexample for one particular interpretation, consider an alphabet with a single symbol $a$, and the language consisting of those words that have even, positive length.

Suppose we have $x,y,z$ with the property that $x y^i z$ is in the language for all integers $i \geq 0$.

We automatically have $y = a^n$, where $n$ is the length of $y$, so we might interpret $y^{1/n} = a$.

But then $xy^{1/n}z$ is not in the language, since it has odd length.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.