a) Almost to the right ...
This grammar generates exactly a lot of lines consisting of balanced parentheses. Try a quick demo to understand why this is so.
First: Everything that comes out of your grammar is a balanced line of parentheses. Why ?, simple induction:
- Epsilon is a balanced (empty) line of brackets.
- if A is a balanced line of brackets, (A) is also balanced.
- If A1 and A2 are balanced, that is, A1A2 (I use identifiers that are too different just to clearly indicate that A → AA is not required, does the same for each A).
Secondly: each set of balanced lines is created by your grammar. Let this be done by induction on the size of the string.
- If the string is zero size, it must be Epsilon.
- If not, then N is the size of the string and M is the length of the shortest prefix that is balanced (note that the rest of the string is also balanced):
- If M = N, you can create this line with (A).
- If M <N you can produce it with A → AA, the first M characters with the first A and the last N - M with the last A. In any case, you need to create a line shorter than N characters, so by induction you can do it. Q.E.D.
For instance: (()()) (())
We can generate this line using the idea of demonstration.
(A) (A)) A → (() ()) A → (() ()) (A) A → (A) (A) - (() ()) ((A)) → (() ()) (())
b) Of course, left and right recursion are enough to say this is ambiguous, but to understand why this particular grammar is ambiguous, follow the same idea to demonstrate:
This is ambiguous because you do not need to take the shortest balanced prefix. You can take the longest balanced (or any balanced prefix in general), which is not the size of the string, and the demonstration (and generation) will follow the same process.
Example: (()) () ()
You can select A → AA and generate with the first substring A (()) or substring (()) ().