Question

1. If the second line in the grammar (definition of S₁) is changed to  

S₁→ aS₁a | bS₁b | A  

will the language generated by the whole grammar change? If yes, give a precise description of the new language. If no, give a clear logical argument explaining why the language will not change.   

                                                                                                                                   

Answer 1

Grammar for the mentioned question is not given.

So, I'm making an assumption that there are two inputs (a&b) and A is the end node.

If we divide the given line then, it'll be

S₁ -> a S₁ a

S₁ -> b S₁ b

S₁ -> A

If we observe this grammar then we can change it into

S₁ -> (a+b) S₁(a+b)

S₁ -> A

And from this, we can conclude that this grammar is checking the length of the entered string should be greater or equal to two.

So, if we add this line into any grammar then it'll definitely change it unless it confirms that length of entered string is greater or equal to two.