Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"

share|improve this question
1  
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... –  hmmmm Oct 20 '12 at 17:03
    
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). –  Hagen von Eitzen Oct 20 '12 at 17:24

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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