CS181 Fall 95 Homework 1 Comments
Last modified: October 23, 1995 3 pm (Wk 4 Monday)
Go to CS181 home page
Go to CS181 Fall 95 homeworks
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.
How to reach Mitchell Tsai
E-mail: tsai@ucla.edu