Section 1

The
following language is ambiguous. Answer questions about how it can interpret
expressions.

E -> E + E | E * E | (E) | N

N -> DN | D

D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

Depending
on how the CFG interprets the input, expressions can be evaluated differently.

For
example, 2*5+1 could mean 2*(5+1)=12 or (2*5)+1=11. The language is ambiguous,
both of these interpretations are correct for this CFG.

Enter all
the different result values for the give expression. Separate the numbers with
commas. If the above example was give, the answer would be 11,12.

Question 1Enter all possible results from evaluating the
expression below. Separate values using commas.

1+5*7+3

Score: 0 out of 10

Question 2Enter all possible results from evaluating the expression
below. Separate values using commas.

7*4*9*10

Score: 0 out of 10

Question 3Enter all possible results from evaluating the
expression below. Separate values using commas.

2*3+4*5

Score: 0 out of 10

Section 2

In the
following section, you will be given 4 CFG and a string. Select all CFG that
accpet the input string. Another way to think about it is, select all CFG that
can generate the string given.

Question 4Which CFG can accept the string 000111 (Select all that
apply)

Score:
7.5 out of 10

M -> 0M1 | epsilon

X -> 0X1X | 1X0X | epsilon

P -> 0P1P | epsilon

S -> 0S0 | 1S1 | 1 | 0 | epsilon

Question 5Which CFG can accept the string 1001 (Select all that
apply)

Score:
2.5 out of 10

M -> 0M1 | epsilon

X -> 0X1X | 1X0X | epsilon

P -> 0P1P | epsilon

S -> 0S0 | 1S1 | 1 | 0 | epsilon

Question 6Which CFG can accept the string 011100 (Select all that
apply)

Score:
0 out of 10

M -> 0M1 | epsilon

X -> 0X1X | 1X0X | epsilon

P -> 0P1P | epsilon

S -> 0S0 | 1S1 | 1 | 0 | epsilon

Question 7Which CFG can accept the string 1110111 (Select all that
apply)

Score:
5 out of 10

M -> 0M1 | epsilon

X -> 0X1X | 1X0X | epsilon

P -> 0P1P | epsilon

S -> 0S0 | 1S1 | 1 | 0 | epsilon

Section 3

Use
the Math Parser to answer
these questions.

Question 8How many times does the Number variable appear in the
parse tree for 1589?

Score:
0 out of 10

Question 9How many times does the Add variable appear in the parse
tree for 1+2+3+(4)?

Score:
10 out of 10

Question 10How many terminal characters appear in the parse tree
for 10*4+8?

Score:
0 out of 10

Get Higher Grades Now

Tutors Online