Theory proof

Question

1. The complement of a finite language is always infinite

2. The complement of an infinite language may be finite or infinite ..

both statements are true .. i can proof using examples .. can someone give me logical theory proof ?

Comments

Yes. It's true. :). But in 1st example, you've  written ab and Input symbol, now is that a hyphen besides input symbol?Say?In the complemented value.

---

No, that is we are eliminating ab from all other string

means (a+b)*-ab

---

Why do you want theoretical proof, its very much logical, imagine wrt. the set theory and you’ll get it.

Answer 1

1. The set of all strings generated by an alphabet is infinite. If our given set is finite, then we have infinity - something finite which is always infinite.

2. This is similar to 1 except that we have infinity - infinity which is undefined, it can be finite or infinite depending on the size of infinity. For example both the set of points on the real line and the set of points on the cartesian plane are infinite but the cartesian plane has infinite points for every point on the real line  { picking 2 on the x-axis defines a line in the cartesian plane but defines a point on the real line)

Answer 2

let us take a example of language

A.L{xɛ{0,1}* ǀ 00 act as a sub string}

so if we take its complement then it will infinite string all those string which does not had 00 as substring which is infinite

B.just think conversely the complement of infinite language which is above in the example may or may not had finite elements.

I THIMK THIS IS SUFFICIENT.

Answer 3

If you are good at 'Set theory' then always consider language is 'set of elements' then i can guess , it would be easy to answer such questions.

1) Take any finite set S={1,2} now ask yourself what would be S' ?

Infinite- finite = infinite.

2) can you predict infinite-infinite = ?    No, you can't say anything .