Provide a grammar to generate strings that are only made of 1’s, where A={0,1}

193 Views Asked by At

My solution so far is as follow:

S -> 1S | 1

Is it necessary to include lambda in this grammar?

Edit:

To further elaborate, my logic is that since lambda is not 1 it does not belong in the grammar and my solution as is, is sufficient enough to properly generate strings of only 1. such as 1,11,111,1111....

Is this logic flawed or is it correct?

1

There are 1 best solutions below

0
On

It depends on what you mean with "strings that are only made of 1's", one could argue that the empty string $\lambda$ is only made of 1's, since every character in it is 1 (basically, universal quantification on an empty set is trivially true).

Therefore, I would say that both languages: $$ L_1 = \{\lambda, 1, 11, 111, \dots\} $$ and $$ L_2 = \{1, 11, 111, \dots\} $$ are correct interpretations of "strings that are only made of 1's", therefore it truly depends on whether you want $L_1$ or $L_2$. If anything, I would pick $L_1$ as to avoid ambiguity I would usually explicitly state that I am interested in non-empty strings if i wanted to denote the language $L_2$.

Hope this helps!