REGEX - GRAMMARS:

Notes on answering this question: - Pay attention to what kind of grammar I ask for (regular, or context free, or some other type). - For instance: if I ask for a regular grammar and you give me some other kind of grammar, then you may lose marks! - In particular, if your regular grammar contains a rule of the form Sab or SD or SD, then this is not a regular grammar and your answer contains an error. - Always clearly specify the start symbol. - The alphabet (set of tokens) of a language cannot contain . is the empty string, that is, an absence of tokens. If your answer contains something of the form T={,} (where T is supposed to be a set of tokens for your language) then your answer is probably wrong and youre probably losing marks. Some of you have not met set notation before, so heres a quick tutorial: - The language determined by the regex /a*/ is { a | n } or equivalently { a | n {0,1,2,} } or equivalently { a | n 0 }. - The language determined by the regex /(a|b)?/ is { a, b, }. - The language determined by the regex /a+b+/ is { ab | m,n 1 } or equivalently { ab | m 1, n 1 } or equivalently { ab | m,n {1,2,3,} }. - The language determined by the English description any nonzero digit is { 1, 2, 3, 4, 5, 6, 7, 8, 9} or equivalently { 1, 2, , 9} or equivalently { n | 9 n 1 } or equivalently { n | 0

19. Consider the grammar G=({S,A,B},{a,b},P,S) with productions SSABAaABBb 1. Give a leftmost derivation for aababba. 2. Draw the derivation tree corresponding to your derivation