CS 3120 Spring 2003
Homework 1
due: April 16, 2003 (via the digital drop box)

1. Write an EBNF grammar for a legal file name on a PC using an MS-Windows operating system. You need to include the possibility of a complete pathname. However, to make things simpler, file names and directory names may only consist of letters, except that file names include one "." with a filetype of up to 3 letters.



2. From Scott, #2.6, here are some productions:
   A -> a E | b A A
   E -> a B | b A | e
   B -> b E | a B B

   For this exercise, consider E to be the start symbol. Show how to derive the following strings. You need to indicate each production that is applied. To distinguish between repeated instances of a nonterminal, use a number. For example, if you apply the 2nd production for A, you may type A -> b A1 A2, then show how A1 and A2 are replaced. You may also use an ordinary 'e' instead of e.

   • ba
   • aababb


3. For the productions in the preceding problem, explain in English what each nonterminal represents.



4. Write a regular expression to capture the following:
   • A course ID at CSU-Hayward -- this means you need the field name (like CS or CHEM), the course number, and the section number
   • The file names generated in problem #1