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"

  • 1
    $\begingroup$ Argue by contradiction, suppose there was a last word $w_n$ then you could just add an a onto this to get a new word... $\endgroup$ – hmmmm Oct 20 '12 at 17:03
  • $\begingroup$ 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). $\endgroup$ – Hagen von Eitzen Oct 20 '12 at 17:24

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.


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.