Need in 3 hours

2.) Consider the following regular expression r1 = (A|...|Z)∗(0|...|9)∗

a. Describe the language defined by r1 in English.

b. Turn r1 into an equivalent finite automaton.

c. Remove ε-moves from the finite automaton.

d. Is the resulting automaton deterministic? Why (not)?

e. Use the automaton to generate a word with at least five letters. Enumerate the state passed during the generation.

f. Use the automaton to recognize the word IN4303. Enumerate the states passed during the recognition.

3.) Given the following program, draw the stack, including all the elements (local variables, parameters, static link, dynamic link) of each activation record after Q is called in the body of C.

Program Bar;

Procedure Top;

var z: integer;

Procedure A(x: integer);

begin

writeln(x+z);

end;

Procedure B(y: integer);

Procedure C(Procedure Q(z:integer))

begin

Q(y);

end;

begin

C(A);

end

begin

z := 7;

B(6);

end

begin

Top;

end

4.) Do the following:

a. Give a BNF syntax for unsigned floating point constants that would allow constants in the allowed-set but not the not-allowed set.

b. Construct a finite state machine that could be used in a lexical analyzer to read in such floating point numbers.

c. Show how this finite state machine can be extended to evaluate the floating point number it reads.

5.) Java Bytecode. Execute the following byte code instructions, starting with an empty stack.

Allowed Set:

1.2

3E4

0.23E-8

Not-Allowed Set:

.123

20.

21.E4

Show the stack after each instruction. If an instruction performs a jump, name the next instruction.

6.) Let G1 be a formal grammar with nonterminal symbols S and E, terminal symbols x, +, ∗, ( and ), start symbol S, and the following production rules:

bipush 21

ldc 5

iconst_4

dup

imul

iadd

isub

ifeq l1

iconst_1

l1: nop

S → E

E → x

E → E + E

E → E ∗ E

E → ( E )

a. Is G1 context-free? Why (not)?

b. Describe the language defined by G1 in English.

c. Give a right-most derivation for the sentence x + (x∗x).

d. Give two different parse trees for the sentence x + x∗x.