Five shortest strings from language $ L = \{0^{i}1^{i}| i \in \mathbb{N} , i > 0\}$

218 Views Asked by At

I am studying for an upcoming exam, with an example question being. Consider the following language,

$L = \{0^{i}1^{i}| i \in \mathbb{N} , i > 0\}$

Over the alphabet $A = \{0,1\}$

What are the five shortest strings in L?

I'm not 100% on how to interpret the language declaration.

Does the ordering of the string matter?

For example if $i =1 $.

Can we have the strings of "01" and "10"?

Or is the ordering of the language definition absolute where 0 must be first followed by a 1?

I have a possible idea for the answer where the ordering is absolute.

"01", "0011", "000111", "00001111", "0000011111"

Any advice would be greatly appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

The ordering is relevant; the language cosists of all words with first some positive number of $0$'s, which is then followed by an equal number of $1$'s. So $10$ is not in your language, but $01$ is. Since we can't have the empty string ($i>0$ is required), you have successfully listed the five shortest strings at the end of your post.