PLC: Assignment #2 (Sample Solution)

Question 1

  1. a cannot be derived, each identifier has a minimal length of two characters as neither <identifier> nor <subsequent identifier> are able to produce the empty string.
  2. a2
    <identifier>
    ---> <initial> <subsequent identifier>
    ---> <letter> <subsequent identifier>
    ---> a <subsequent identifier>
    ---> a <subsequent>
    ---> a <digit>
    ---> a2
    
  3. 2a cannot be derived as <initial> does not produce digits.
  4. ?a?
    <identifier>
    ---> <initial> <subsequent identifier>
    ---> <special initial> <subsequent identifier>
    ---> ? <subsequent identifier>
    ---> ? <subsequent> <subsequent identifier>
    ---> ? <initial> <subsequent identifier>
    ---> ? <letter> <subsequent identifier>
    ---> ?a <subsequent identifier>
    ---> ?a <subsequent>
    ---> ?a <initial>
    ---> ?a <special initial>
    ---> ?a?
    
  5. @a@ cannot be derived as <initial> does not produce @.

Question 2

<List> ---> ( <ListOfElements> )
<ListOfElements> ---> <empty> | <CommaSeparatedList>
<CommaSeparatedList> ---> <Element> | <Element> , <CommaSeparatedList>
<Element> ---> <List> | <Digits>
<Digits> ---> <Digit> | <Digit> <Digits>
<Digit> ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Andreas F. Borchert, March 25, 2002