David Golombek
6.035 pset #2
TA: Jeremy Brown
Problem 1

The set of languages this class of grammars generates is the same as
that of context-free ones.  This can be simply shown by demonstrating
each of the rules used in regexps in terms of context-free grammar
productions.   
Thus, the regexp 'B^*' can be done in context-free grammars as:

A -> |
     B 

E -> |
     A E 

The regexp 'AB' is done in a CFG as:

E -> A B

Any structure embedded in ()'s in a regexp can be reduced to an regexp
embedded in the surrounding regexp, and matched using these same rules.

Epsilon translates to the empty string in CFG's.
The '|' symbol is simply translates to a '|' in CGF's.

The notational shorthands of +, ? and [] can both be rewritten
entirely in regexps to be done as the parts shown above, so need not
be handled separately.

Thus, because we can handle all notations used in regular expressions,
the two languages are equivalent.


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 2

I choose statement and expression as my major nonterminals.

2a) Here it would work fairly well, skipping over the addition, and
dealing with the assignment correctly.

2b) Here it would again do fairly well, skipping over the second
assignment, but getting the first correctly.

2c) Here it would do very well, only skipping the single semicolon,
but translating everything else perfectly.

2d) Here it would deal poorly, scanning all the rest of the input
string, searching for a then.

2e) Here it would deal poorly, scanning all the rest of the input
string, searching for a fi, but never generating an error until it
unexpectedly hits the end of file.


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 3

Add the productions

<statement> ::= error ';'

and change the if production to be:
<statement> ::= if <then-expression> <statement-list> fi
<if-expression> ::= <expression> then
<if-expression> ::= error then

2a) This would work the same as above.

2b) This would work the same as above.

2c) This would work the same as above.

2d) This would be handled well, seeing the error, and finishing the
if-then-fi product.

2e) This would work the same as above.


David Golombek
6.035 pset #1
TA: Jeremy Brown
Problem 4

4a) This is neither, because there is no way of keeping track of the
number of 0's before the 1's occur.

4b) 10(1|0)(1|0)(1|0)(1|0)(1|0)(1|0)01

4c) No, this is neither regular nor representable by a CFG.  You can
never determine if the number of 1's is prime.

4d) No, this is neither, because there is no way of associating the
n before the H and the number of 0's, because a parser can't do a
string to integer conversion.