Quiz Solutions
Each quiz is out of 3 points. The 3 worst quiz grades are dropped at the end of term.
Quiz #15 (27 Apr)
Minimize this DFA:
Solution:
Group 1 Group 2
(Non-accepting) (Accepting)
--------------- -----------
0, 2, 4 1, 3, 5, 6
On a: | / \
0, 2, 4 1, 3 5, 6
On b: / \ | |
0 2, 4 1, 3, 5, 6
On a again: no change
On b again: no change
Both DFAs corresponded to the regex a|b((a|b)(a|b)+)?
Quiz #14 (25 Apr)
Construct a DFA from this NFA:
Solution:
Both NFA and DFA corresponded to the regex a+c*b*
Quiz #13 (13 Apr)
Provide a grammar for {a3b3nc4nd5 | n >= 0}.
S -> aaaXddddd
X -> bbbXcccc | ε
This could also be written this way:
S -> a3Xd5
X -> b3Xc4 | ε
Quiz #12 (11 Apr)
1. Construct a parse of : a*a+a*a.
SYMBOL STATE INPUT* TRANSITION/REDUCTION
1. [empty] 0 a*a+a*a| Initial state
2. a 0 4 *a+a*a| "a" trans from 0 to 4
3. T 0 3 *a+a*a| T->a reduction
4. T * 0 3 5 a+a*a| "*" trans from 3 to 5
5. T * a 0 3 5 7 +a*a| "a" trans from 5 to 7
6. T 0 3 +a*a| T->T*a reduction
7. E 0 1 +a*a| E->T reduction
8. E + 0 1 2 a*a| "+" trans from 1 to 2
9. E + a 0 1 2 4 *a| "a" trans from 2 to 4
10. E + T 0 1 2 6 *a| T->a reduction
11. E + T * 0 1 2 6 5 a| "*" trans from 6 to 5
12. E + T * a 0 1 2 6 5 7 | "a" trans from 5 to 7
13. E + T 0 1 2 6 | T->T*a reduction
14. E 0 1 | E->E+T reduction
15. ACCEPT
2. What happens if you try to parse a non-sentence, such as a+aa?
You reach a state with no edge matching the next input symbol. For the given example, you reach state 4. The only legal departure from this state is by applying the "T->a if {*,+,|}" reduction. However, the next input symbol would be the final "a", which means the rule does not apply.
Midterm (23 Mar)
1.) sub1 PROC push bp mov bp, sp mov ax, [bp+6] ;a) put the value of Y into AX mov bx, [bp+4] mov cx, [bx] ;b) put the value of Z into CX pop bp ret 6 sub1 ENDP 2.) mov ax, A cmp ax, B jne NOT_EQUAL mov ax, T mov R, ax jmp DONE NOT_EQUAL: mov ax, S mov R, ax DONE: 3.) ;copy MES1 to MES2 w/ string handling and no loops push ds pop es cld mov si, offset mes1 mov di, offset mes2 mov cx, 20 rep movsb 4.) mov cx, 20 mov bx, 0 COPY_BYTE: mov al, [mes1 + bx] mov [mes2 + bx], al inc bx loop COPY_BYTE 5.) ABS MACRO X local DONE mov ax, X cmp ax, 0 jge DONE neg ax ;neg to pos value DONE: ENDM ABS 6.) fld A fld B fmul fld C ;(tho C is a reserved word) fld D fmul fsub fstp E 7.) ;assuming already in graphics mode: ax = 0013h, int 10h push 0A000h pop es mov di, (320 * 40) + 130 ;starting at top of triangle mov al, 04h ;red pixel mov cx, 60 LEFT_SIDE: stosb add di, 318 ;after stosb, to get 319 total loop LEFT_SIDE BOTTOM: mov cx, 120 ;60 back to center, then 60 more rep stosb mov cx, 60 RIGHT_SIDE: stosb sub di, 322 ;after stosb, to get -321 total loop RIGHT_SIDE
Quiz #11 (14 Feb)
Write the code to:
a) Get into graphics mode
b) Draw a red horizontal line of length 150 pixels, whose left-hand end is at COL 40, ROW 60 (in pixels!).
;a) mov ah, 00h mov al, 13h int 10h ;get into graphics mode ;b) mov ax, 0A000h ;direct memory access mov es, ax mov al, 04h ;a red byte mov di, (60*320 + 40) ;row 60, col 40 mov cx, 150 ;draw 150 pixels rep stosb
Though not covered in lecture, another way to draw a graphical line (part b) is:
mov ah, 0Ch ;draw pixel mov bh, 0 ;set/clear page mov al, 04h ;a red byte mov cx, 40 ;column mov dx, 60 ;row draw: int 10h inc cx ;move over one column cmp cx, 40+150 ;destination jl draw
Quiz #10 (09 Feb)
Given:
X1 DD ?
X2 DD ?
...
X9 DD ?
Evaluate using floating point instructions:
Y = (x1 * x2 * x3 - x4 * x5 * x6)/(x7 * x8 * x9)
fld x1 fld x2 fld x3 fmul fmul ;st(0) = (x1 * x2 * x3) fld x4 fld x5 fld x6 fmul fmul ;st(0) = (x4 * x5 * x6) fsub ;st(0) = (x1 * x2 * x3)-(x4 * x5 * x6) fld x7 fld x8 fld x9 fmul fmul ;st(0) = (x7 * x8 * x9) fdiv fstp Y
Quiz #9 (07 Feb)
1. Given: buf DB 240 dup(?)
Write the code to initialize buf to 00h bytes. Do this using the "rep" prefix together with a string-manipulation function.
;assuming ds == es cld mov cx, 240 lea di, buf mov al, 00h rep stosb
2. Write a macro to put the largest of 3 word arguments into AX.
largest MACRO A, B, C LOCAL CmpC, Done mov ax, A cmp ax, B jge CmpC mov ax, B CmpC: cmp ax, C jge Done mov ax, C Done: ENDM
Quiz #8 (02 Feb)
Write a main program and a separately compiled subprogram called Sub1 which evaluates 2(X-Y). In the main program:
X DW ?
You must code this using the standard method emplyed by all commercial compilers. Your subroutine should be: call by value, args pushed from left to right, sub fixes up the stack, near program.
Y DW ?
;main.asm EXTRN Sub1:NEAR .MODEL small .586 .STACK 100h .DATA X DW ? Y DW ? .CODE Main PROC mov ax, @data mov ds, ax ... push X push Y call Sub1 ... Main ENDP END Main
;sub1 PUBLIC Sub1 .MODEL small .586 .CODE Sub1 PROC ;2(X-Y) push bp mov bp, sp mov ax, [bp + 6] sub ax, [bp + 4] shl ax, 1 pop bp ret 4 ;answer in ax Sub1 ENDP END
Quiz #7 (31 Jan)
Write a main program which calls a separately compiled program SLAVE2 to evaluate 2(X+Y). Arguments are to be passed using the PUBLIC/EXTRN mechanism. Then write SLAVE2.
;main.asm EXTRN SLAVE2:NEAR EXTRN X:BYTE, Y:BYTE .MODEL small .586 .STACK 100h ... .CODE Main PROC ... mov X, al ;load X and Y somehow ... mov Y, al call Slave2 ;answer in al ... Main ENDP END Main
;slave2.asm PUBLIC Slave2 PUBLIC X, Y .MODEL small .586 .DATA X DB ? Y DB ? .CODE Slave2 PROC ;2 * (X+Y) mov al, X add al, Y shl al, 1 ret ;answer in al Slave2 ENDP END
(The global variable X and Y can be declared in either file. Since their primary use here is to pass values to Slave2, I thought it most logical to define it in that file.)
Quiz #6 (26 Jan)
Write the code to input a name of up to 15 characters and then output on a new line "Your name is" followed by the inputted name.
.DATA
prompt DB "Enter your name: $"
prompt2 DB 10, 13, "Your name is $"
inBuff DB 16, ?, 16 DUP('$'), '$' ;room for 15 chars + CR
.CODE
...
mov ah, 09h
lea dx, prompt
int 21h
mov ah, 0Ah
lea dx, inBuff
int 21h
mov ah, 09h
lea dx, prompt2
int 21h
lea dx, [inBuff + 2]
int 21h
...
Quiz #5 (24 Jan)
Insert code to branch to the appropriate label depending on the value in AX.
.DATA N DW ? ... .CODE ... add ax, N cmp ax, 0 je ZERO_CASE ;the 3 lines you need jl MINUS_CASE jg POSITIVE_CASE ZERO_CASE: ... MINUS_CASE: ... POSITIVE_CASE: ...
Quiz #4 (19 Jan)
Given:
LIST3 DW 19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7
ANSWER DW ?
Write the code to add the numbers in List3. Preferably use the EQU operator in the Data segment to avoid having to count how many numbers List3 contains.
One way to do it:
.DATA LIST3 DW 19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7 ANSWER DW ? NUM EQU ANSWER - LIST3 .CODE ... mov bx, NUM - 2 ;last element in LIST3 mov cx, NUM / 2 ;number of elements in LIST3 Sum: mov ax, [LIST3 + BX] add ANSWER, ax sub bx, 2 dec cx jnz Sum
Another way to do it:
.DATA LIST3 DW 19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7 LAST DW $ - LIST3 - 2 ANSWER DW ? .CODE Main PROC mov ax, @data mov ds, ax mov ax, 0 mov bx, LAST Sum: add ax, [LIST3 + bx] sub bx, 2 jge Sum mov ANSWER, ax
And still another:
.DATA LIST3 DW 19, 8, 20, 14, 17, 22, 15, 1, 3, 8, 7 ANSWER DW ? .CODE ... lea bx, LIST3 ;start of LIST3 mov ax, 0 Sum: add ax, [bx] add bx, 2 ;to next LIST3 index cmp bx, offset ANSWER ;if still in LIST3 jb Sum mov ANSWER, ax
Quiz #3 (17 Jan)
1) The four 32-bit general registers: EAX, EBX, ECX, EDX.
2) For one 32-bit general register, show the 16 and 8-bit registers that form part of it.
For EAX:
---------------- -------- --------
| | AH (8) | AL (8) |
---------------- -----------------
^ <== AX (16) ==> ^
3) Besides the general registers, what other registers can be specified as operands?
The segment (CS, DS, ES, FS, GS, SS), pointer (BP, SP), and index (SI, DI) registers. (Basically, everything but IP and FLAGS can be manipulated directly.)
Quiz #2 (12 Jan -- Speed Test)
1) 6 = 0110b 9 = 1001b Ah = 1010b Dh = 1101b 2) 2^5 = 32 2^8 = 256 2^3 = 8 2^11 = 2,048 3) 1110b = Eh 0101b = 5h 1011b = Bh 1100b = Ch
Quiz #1 (12 Jan)
1) 2^9 = 512
2) 257,982 = Binary: 0011 1110 1111 1011 1110b
Hex: 3EFBEh
3) 0 1001 1010 1011 = Hex: 9ABh
Decimal: 2,475
4) 10 1101 1000
+ 00 1110 0110
11 1011 1110
5) 2FD03Fh
+ 3EE247h
6EB286h