Good evening everyone, I was doing the second exercise of the exam session held on 22th February 2024 and I was wondering if the CFG in the solution is right, because I think you cannot be sure to get two strings x and y with equal length.
In the picture I show my CFG.
I think your CFG and the one in the solution are actually the same.
In the solution, the production S → T S T generates a balanced string, because it adds one symbol on the left and one on the right. Since T → a | b, each of these symbols can be either a or b.
These are exactly all the cases you wrote (aSa, aSb, bSa, bSb).
I hope this helps.
I think I get what you are saying, but I am not so sure about it. How can you be sure that the T on left side generates a string of the same length of the string generated by the T on the right side? Maybe I am still missing something.
Cause T only leads to terminals, so in either cases it becomes a string of length 1. The way the solution generates string of equal length is by adding several T’s by the same amount on each side of the S