Theory of computation Revision Exercises

Question 3 - Using Context-Free Grammars (20 points) (a) [10 points] Using grammar G below give the leftmost derivation of the string abb!abbaba S a b S Ab a b A B! B able C + DE D + ab E bale (b) (10 points] Using grammar G below construct a leftmost and a rightmost derivation of the input string dbaabffae as well as the parse tree for the derivations. S BSS | BBS | CSB | Lef L + Sal B + aCbC C + eB