Part 2- Context-Free Grammar (9 points) In this part, we will be working with context-free grammar. Part (d) and (e) concern about derivations. Our textbook has mentioned the term, but it does not give concrete examples on how a derivation looks like. The following is a very simple example Assuming our (context-free) grammar is the following: SABC Note that in this grammar, the starting symbol is S. A, B, C, and S are non- terminal symbols, while e, a, b, and c are terminal symbols. To show that the string abbc belongs to this grammar, we can do a leftmost derivation SABCaABCaBC abBCabbBC abbC abbcCabbc 4 Note that both the dollar sign character () and the dot( character are special characters in regular expressions and hence need to be escaped. Spring 2019 SC322 Assignment 1 STATE UNIVERSITY Programming Languages Fayetteville State University Albert Chan Page 3 of4 FAYETTEVILLE Or we can do a rightmost derivation Given the following context-free gramm for a biary number: BinaryNumber Sign NonNegativeValue 0 PositiveValue PositiveValue NonZeroDigit Digit Sign NonNegativeValue NonZeroDigit | Positive Value Digit (a) (2 points) Identify the non-terminal symbols (b) (2 points) Identify the terminal symbols (c) (1 point) Identify the Start symbols (d) (2 points) Perform a step-by-step (one substitution per step) leftmost derivation to show that -10110 is binary number (e) (2 points) Perform a step-by-step (one substitution per step) rightmost derivation to show that-10110 is binary number