Specifying language for a given grammar

Question

DFA problem : Write a complete grammar for L, including the quadruple and the production rules

L ={x: ∃y ∈ {a, b}* : x = ay}

Answer:

G={{S, A}, {a, b}, S, P}
P: S => aA
   A => aA | bA | λ

My question is :

1. Why there is λ for A, but there is no λ for S?
2. From the language definition, it is any string that begins with an a and contains only a's and b's , but why in the answer A => bA. Does not it mean that the string starts with b if it is A => bA?

Thank you so much

Answer 1

1. Why there is λ for A, but there is no λ for S?

λ nul can be derived from A to convert a sentimental from into sentence. Additionally according to language statement prefix sub-string y ∈ {a, b}* can be nul (a empty string) e.g. "a" is a string belongs to the language. If y contain any symbol then length of language will be more than one.

S doesn't derive λ nul because empty (or say nul string) is not in language. The smallest string in language is single "a".

2. From the language definition, it is any string that begins with an a and contains only a's and b's , but why in the answer A => bA. Does not it mean that the string starts with b if it is A => bA?

Note only strings those can derived from start variable S are included in language of grammar. You can't start derivation from A (that is not start variable). And if you start a derivation from S your string will always start with a symbol.

I suggest you to read: "Why the need for terminals? Is my solution sufficient enough?" Where I written about basic definition of formal grammar.