CS181 Fall 95 Homework 1 Comments

Last modified: October 23, 1995 3 pm (Wk 4 Monday)

Statistics

• 46 people turned in hw1, 51 enrolled
• 100 high, 93 75-percentile, 86 median, 81 25-percentile, 48 low
• 84 average
  
  
• Point Distribution : 7 points on every problem except for 1f, 2a, and 2b (which are 10 points).

Solution 1 Errors

• Problem 1d Under states: arrow on the left of q0, asterisk on the left on q4
• Problem 3c (3,e) should read (3,epsilon)
  Does anyone know how to draw an epsilon, sigma, or subscript in HTML?

Comments and Most Common Errors

• Problem 1a Leaving out the start arrow
• Problem 1a Don't forget to check the alphabet! A few people wrote arrows for all the 0 transitions.
• Problem 1a Omitting states q4 to q20 is permitted. Please leave enough states to show a pattern.
• Problem 1a-c, 2a-b Some people wrote a non-deterministic FSA (NFSA).
  A deterministic FSA (DFSA) must satisfy the following:
  
  • Each state must have 1 exit arrow for every alphabet letter.
  • Abbreviations like 0-9 and sigma are allowed. Please don't say "else".
  • It does not matter whether the machine has a "dead" state.
• Problem 1b No leading zeroes
• Problem 1c Leading zeroes are allowed; i.e. 0010010, but epsilon (empty string) is not.
• Problem 1c 0 is not positive
• Problem 1d In transition tables, Start states have arrows on the left, Accept states are asterisked on the left (in the States column only).
• Problem 1d In transition tables, every state must appear (including "dead" states).
• Problem 1e, 3a Don't forget the M = {Q, sigma, delta, q0, F} to define the machine.
• Problem 1e, 3a If you use a table for delta, label the table with delta:.
• Problem 1e, 3a Use curly braces for sets : {a,b,c}
• Problem 1e, 3a F is a set of states
• Problem 1e, 3a For a DFSA, q0 is a single state. For an NFSA, q0 is a set of states.
• Problem 1e Don't do L2 instead of L3!
• Problem 2a No leading zeroes
• Problem 2a A SIGNED INTEGER must start with a +/-; e.g. +0 and -0.
• Problem 2b No leading or tailing zeroes; i.e. 3.001 and 0.0 are acceptable, but 03.00 is not.
• Problem 3b Some calculations were REALLY long. If you are very clear, you can skip many steps. Skipping all the steps is only dangerous if the problems says "Show the computation, as in 3c" or you make a mistake (It's harder to give partial credit).
• Problem 3c Please use yield symbols in your ID computations, and say "accept" or "reject"
• Problem 3e "No blocks of b's" is not accurate.
• Problem 3e Many incorrect regular expressions fail on abaabaa.