Exam-style question
Try this first
Explain the meaning of the set {0^n1^n | n ≥ 1} and list its first four strings. Also state whether this set is finite or infinite and justify your answer.
Model answer
What a good answer should say
- The notation describes all strings consisting of n zeros followed by n ones, where n is a natural number of at least 1.
- The first four strings are 01, 0011, 000111 and 00001111.
- The set is infinite because there is a valid string for every natural number n ≥ 1, so the strings continue without a final member.
Explanation
Why this works
The same value of n determines the number of zeros and the number of ones. Increasing n produces another string, so no particular final string exists.
This makes the set infinite. The notation does not describe arbitrary arrangements of zeros and ones; all zeros occur before all ones.
Common mistake
No common mistake is linked to this question yet.