Prove a language is not regular. Use pumping lemma.

Question

I have the language G = {fff|f is in {t,u}*}

My proof is as follows,

Assume G is regular. Since it's regular, the pumping lemma says that for s in A of length of at least p, it must be able to be divided into s = xyz such that it satisfies three conditions: 1) xy$^i$z in G for i >= 0

2) |y| > 0

3) |xy|<= p

Let s = $t^put^put^pu$

Since |xy| <=. the string xy contains nothing but t's up to p. In other words, xy = t$^h$ for some 0 < h <= p

Let x = t$^j$ for some j >= 0,

y = t$^k$ for some k > 0 z = t$^{p-(j+k)}$ut$^p$ut$^p$u

Let i = 0 such that xy$^i$z = xz

xy$^0$z = xz = t$^{p-k}$ut$^p$ut$^p$u

The string t$^{p-k}$ut$^p$ut$^p$u will be in G only if p-k is equal to p1, the number of strings from the second f, and p2, the number of strings from the third f. Since k > 0, there are no k such that p-k = p1 = p2. In other words, t$^{p-k}$ut$^p$ut$^p$u is not in G which contradicts the first statement of the pumping lemma. Thus G is not regular.

How is this proof? And what if I were to do this so that f = t$^p$ or f = u$^p$. I feel like I would also get something similar would I not?

Answer 1

First and foremost, it's good. The thrust of the proof works, and you seem to be clear on the underlying logic.

That said, it's time for nit-picking! The art of formally writing a proof is often the more troublesome skill to learn when learning to prove things. Students can often grasp the underlying logic, but struggle to put it to paper formally, or at least struggle with conventions.

My first criticism, is your introduction of $p$. What is $p$? Yes, it's stated on the Wikipedia page on the Pumping Lemma, but this is a dummy variable in the statement of the theorem! You shouldn't rely on people knowing what $p$ is, because some people may state the theorem with a different pronumeral (e.g. $n$).

I would start your proof along the lines of

Assume $G$ is regular. Since it's regular, the pumping lemma states that there exists an integer $p \ge 1$ such that, for all $s \in G$ with $|s| \ge p$, there exist $x, y, z$ such that

1. $s = xyz$
2. $|y| > 0$
3. $|xy| \le p$
4. $xy^iz \in G$ for integers $i \ge 0$.

Secondly, where you write,

Since |xy| <=. the string xy contains nothing but t's up to p. In other words, xy = t$^h$ for some 0 < h <= p,

I would write the other words instead, as they seem clearer to me, so

Since $|xy| \le p$, $xy = t^h$ for some $0 < h \le p$.

Finally, the last paragraph could be made clearer:

The string t$^{p−k}$ut$^p$ut$^p$u will be in G only if p-k is equal to p1, the number of strings from the second f, and p2, the number of strings from the third f. Since k > 0, there are no k such that p-k = p1 = p2. In other words, t$^{p−k}$ut$^p$ut$^p$u is not in G which contradicts the first statement of the pumping lemma. Thus G is not regular.

Note also in this paragraph, introduction of $f$. Again, $f$ is a dummy variable used in the definition of $G$. It's a good idea to use this variable, but you should properly introduce it. Say something along the lines of,

Because $t^{p−k}ut^put^pu \in G$, there exists an $f \in \lbrace t, u \rbrace^*$ such that $fff = t^{p−k}ut^put^pu$.

Here's how I would write out the final paragraph:

Let $s' = t^{p−k}ut^put^pu$. Because $s' \in G$, there exists an $f \in \lbrace t, u \rbrace^*$ such that $fff = s' = t^{p−k}ut^put^pu$. Since $u$ occurs exactly three times in $s'$, it follows that $u$ occurs exactly once in $f$. Since $u$ is the last letter of $s'$, it follows that $u$ is the last letter of $f$. Hence, for some $n \ge 0$, we have $f = t^n u$, and thus $$t^{p−k}ut^put^pu = fff = t^n u t^n u t^n u.$$ Looking at the number of consecutive $t$s beginning each string, we must therefore conclude that $p - k = n$. Similarly, if we remove the common tailing $u$ and consider the number of $t$s ending each string, we similarly conclude that $p = n$. Combining these yields $k = 0$, which contradicts $k > 0$. Therefore, by contradiction, $G$ is not regular.