The language of set expressions defined as follows:

A a comma-separated list of zero or more names enclosed in curly braces is a set expression.

If S1 and S2 are both set expressions, then so are each of the following:

S1 ? S2 S1 ? S2 S1 - S2 ( S1 )

In a set expression, parenthesis has the highest precedence; intersection and union have the same, second highest precedence; subtraction has the lowest precedence. Intersection, union and subtraction are all left associative.

the following table are tokens for terminals:

NAME // one name in a set ? // union ? // intersection - // minus ( // left paren ) // right paren { // left curly brace } // right curly brace , // comma 

This time you are not required to write CFG for this language, some CFGs are offered below. For each CFG, do the following check:

If there exists one string that is a legal set expression (given our definition above), but is not in the language of the CFG, give one example.

If there exists one string that is not a set regular expression (given our definition above), but is in the language of the CFG, give one example.

If the CFG is ambiguous, drawing two different parse trees for some string in the language of the CFG.

If the CFG is correct, claim "It is correct".

Note that the terminals are LPAREN, RPAREN, MINUS, UNION, INTERSECT, LCURLY, RCURLY, COMMA and NAME.

CFG 1:

exp ? exp MINUS term | term term ? term UNION factor | term INTERSECT factor | LPAREN exp RPAREN | factor factor ? LCURLY list RCURLY list ? NAME | list COMMA NAME 

CFG 2:

exp ? LCURLY RCURLY | LCURLY list RCURLY | term term ? term MINUS factor | factor factor ? factor UNION set | factor INTERSECT set | set set ? LPAREN set RPAREN | exp list ? epsilon | NAME | list COMMA NAME 

CFG 3:

exp ? exp MINUS term | term term ? term UNION factor | term INTERSECT factor | LPAREN exp RPAREN | factor factor ? LCURLY RCURLY | LCURLY list RCURLY list ? NAME | list COMMA NAME 

CFG 4:

exp ? exp MINUS term | term term ? factor UNION factor | term INTERSECT factor | factor factor ? LPAREN exp RPAREN | LCURLY RCURLY | LCURLY list RCURLY list ? NAME | list COMMA NAME 

CFG 5:

exp ? exp MINUS term | term term ? term UNION factor | term INTERSECT factor | factor factor ? LPAREN exp RPAREN | LCURLY RCURLY | LCURLY list RCURLY list ? list COMMA NAME | NAME