3
$\begingroup$

I'm having trouble with the following exercise:

Let $\Sigma = \{a,b,c\}$ and $L$ be a formal language, that consists of all words which contain all three letters at least once. Show that $L$ is infinite.

I figured out that I could define a word

$w_0 = abc, w_0\in L$

so the condition is met, and then say

$w_i = w_0\cup_{i = 1}^{\infty}a, w_i \in L$

..which shows that you could add infinitely many letters(a's in this case) to it and therefore you can get infinitely many words.

Now I don't know how to show that the rule above does indeed produce infinitely many words, isn't it just obivous? I'm also not sure about the notation - should I just add "This shows that L is infinite" ? And finally I don't know if I'm allowed to use a specific pre-condition like "abc"

  • 0
    Though you cannot add *infinitely* many letters to $w_0$, you can only add *arbitrarily many* letters to it (which gives you *infinitely many* different words).2012-10-20

1 Answers 1

4

One way to formally prove that a language is infinite is to give an explicit mapping from $\mathbb{N}$ to $L$ which maps every $n$ to a distinct word $w \in L$. Using your reasoning about words $a\ldots abc$, you could use $f: \mathbb{N} \to L$, $ n \to a^nabc $

Now, since the length $|f(n)|$ of $f(n)$ is $3+n$, $f(n) \neq f(m)$ if $n \neq m$, since words with different lengths cannot be equal. $f$ thus has the necessary propertiers, hence $L$ is infinite.

Note that his is pretty much exactly your proof, just worded a bit differently.