(b) In this question, we consider CFGs in which we takeSto be the initialvariable. For each of the following statements, state whether they aretrue or false. Correct answers are awarded4marks; wrong answersare penalised by1mark (to a minimum of0marks for this question).Omitted answers do not contribute positively or negatively to your grade.[16 marks]i. The CFG over the alphabet{a, b,=,+,1,;}with reductionsSA;SAa=EAb=EEaEbE1EV+VTrue or false: the language of this CFG is infinite (meaning: containsinfinitely many strings).ii. The CFG over the alphabet{(,)}with reductionsS(S)S(SS)S()True or false: the language of this CFG is precisely the set ofnon-empty strings over{(,)}with balanced brackets, includinge.g.(),(()),(()(())), ...iii. The CFG over the alphabet{(,)}with reductionsS(T)ST(T)S(T((T)T))STSTrue or false: the language of this CFG is precisely the set of(possibly empty) strings over{(,)}with balanced brackets, includinge.g.(),(()),(()(())), ....

v. The CFG over the alphabet{a,!}with reductionsSHSHSSaH!!SHSHSTrue or false: the CFG is left-recursive

(b) In this question, we consider CFGs in which we take S to be the initial variable. For each of the following statements, state whether they are true or false. Correct answers are awarded 4 marks; wrong answers are penalised by 1 mark (to a minimum of 0 marks for this question). Omitted answers do not contribute positively or negatively to your grade. [16 marks] i. The CFG over the alphabet {a,b, =, +, 1,;} with reductions S+A;8|1 a=E|1 +6=E|E+a|E+6E+1|E +V+V True or false: the language of this CFG is infinite (meaning: contains infinitely many strings). ii. The CFG over the alphabet {(,)} with reductions S +(5) | S + (SS) | S+() True or false: the language of this CFG is precisely the set of non-empty strings over {()} with balanced brackets, including e.g. 0, 0), (0(0)),... ii. The CFG over the alphabet {(,)} with reductions $+(T) | S +T(T) | S + (T((T)T) | S + | T +S True or false: the language of this CFG is precisely the set of (possibly empty) strings over {()} with balanced brackets, including e.g. (),(0), (000)),.... 2 Compilers and Computer Architecure G5035 iv. The CFG over the alphabet {a,!} with reductions S+HSHS | S +aH!! | S + | H+SHS True or false: the CFG is left-recursive