Quiz Solutions
Each quiz is out of 3 points. Your 3 worst quiz grades are dropped at the end of term.
Quiz #14 (26 Apr)
1. Construct a NFA using the mechanical method for a(b|c)*|b*.
2. Construct a minimal-state DFA equivalent to the following DFA:
NON-ACCEPT ACCEPT 1,3,4,6 2,5 a) / \ / 3,4 1,6 2,5 b) \ | | 3,4 1,6 2,5 a) / \ | 3,4 1,6 2,5 b) \ | / 3,4 1,6 2,5
Quiz #13 (24 Apr)
Use the mechanical method of construction to produce a NFA for (a|b|c)+.
Following a purely mechanical approach using only the seven building blocks given in lecture would produce this: ((a|b)|c)((a|b)|c)*
However, if we had a building block for a 3-way "or" (R|S|T) and a "+" closure, we could produce this directly: (a|b|c)+
Quiz #12 (10 Apr)
Produce a parse of a*a*a+a using the parsing machine [as given in the
Set 24 notes].
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. T * 0 3 5 a+a| "*" trans from 3 to 5
8. T * a 0 3 5 7 +a| "a" trans from 5 to 7
9. T 0 3 +a| T->T*a reduction
10. E 0 1 +a| E->T reduction
11. E + 0 1 2 a| "+" trans from 1 to 2
12. E + a 0 1 2 4 | "a" trans from 2 to 4
13. E + T 0 1 2 6 | T->a reduction
14. E 0 1 | E->E+T reduction
15. ACCEPT
("|" = end of file)
Quiz #11 (22 Feb)
1) (OPEN BOOK) Provide the code required to produce the output shown from clock 1:
; program clock 1 to produce a 250 hz signal (following example code format) mov al, 01110110b ;initialize timer clock 1 out 43h, al mov ax, 4 ;divide 1000hz input by 4 to get 250hz output out 41h, al ;clock 1 on port 41h, send low byte of divisor mov al, ah out 41h, al ;send high byte of the divisor
2) (CLOSED BOOK) Describe the set of signals that occur when you press a key and how the interrupt routine for the keyboard gets executed:
Key pressed goes to UART UART signals interrupt controller IC interrupts CPU (if current routine can be interrupted by keyboard), specifying that a keyboard interrupt occurred CPU finishes current instruction, and then saves state (next instruction and flags) CPU calls system subroutine for handling keyboard input CPU/Subroutine acknowledges IC CPU reads data from UART along data bus CPU returns to stored next instruction
Quiz #10 (20 Feb)
Assuming graphics mode 13h, determine the COL and ROW of the point indicated (front of top/right tail gun). (Image not to scale.)
Nose (point): COL 200, ROW 100
Body (length): 50 pixels
Tail wing (diagonal length): 40 pixels (20 each side)
Gun: triangle with horizontal base of 7 pixels, attached 5 pixels from the body.
Since we know the location of nose, we just determine the offset from there. COL/x = 200 (nose) + 50 (body) - 5 (tail wing) - 7 (gun base) = 238 ROW/y = 100 (nose) + 0 (body) - 5 (tail wing) - 0 (gun base) = 95 Answer: COL 238, ROW 95.
Quiz #9 (15 Feb)
Write the code to draw, in graphics mode 13h, a horizontal line of length 10 pixels, colored red (color code: 04h) whose left-hand end is at COL 40, ROW 60 of the graphics screen.
mov ax, 0A000h mov es, ax ;so di now points into video memory mov ah, 00h ;get into graphics video mode mov al, 13h int 10h mov di, (60 * 320) + 40 ;row 60, col 40 (indexed from 0) mov al, 04h ;red pixel mov cx, 10 ;line of length of 10 pixels cld ;draw forward (left to right) rep stosb
Quiz #8 (13 Feb)
Color codes: Yellow is Eh, red is 4h. Write a red 'D' on a yellow background at COL 32, ROW 9 by writing directly into video memory (ie, not using the int instruction). Text-based video memory starts at 80000h B800h.
mov ax, 0B800h mov es, ax ;so di now points into video memory mov ah, 00h ;get into text video mode (optional) mov al, 03h ;(also clears screen) int 10h mov di, 2 * ((9 * 80) + (32)) ;row 9, col 32 (if indexed from 0) mov ah, 0E4h ;yellow backround, red foreground mov al, 'D' ;letter D stosw
Quiz #7 (01 Feb)
Write a macro called COMP such that COMP X, Y, N compares the first N bytes of string X and Y, and sets AX = 1 if they are equal or AX = 0 if they are not equal. No checking needs to be made as to whether the lengths of X and Y are <= N or that X and Y are strings.
Example of use: COMP MES1, MES2, 5
;Compares the first N characters of 2 strings (X and Y) for equality. ;If equal, sets AX = 1; else AX = 0. ;Does not preserve registers, so will also trash: ES, SI, DI, CX, and flags COMP MACRO X, Y, N LOCAL MATCH, DONE ;to avoid duplicate label error ;if macro is used more than once push ds pop es ;so di in same segment as si lea si, X lea di, Y mov cx, N cld ;ensure we'll go forwards repe cmpsb jcxz MATCH ;cx==0, so matched all of N chars mov ax, 0 ;else... jmp DONE MATCH: mov ax, 1 DONE: ENDM COMP
Quiz #6 (30 Jan)
Assuming:
.DATA M DW ? N DW ? ... .CODE Main PROC ... push M push N call ADDER ... Main ENDP
Write the subroutine ADDER to set AX = M + N. Use the standard subroutine form.
Adder PROC push bp mov bp, sp mov ax, [bp + 6] ;M add ax, [bp + 4] ;N pop bp ret 4 Adder ENDP
Quiz #5 (25 Jan)
Write the code to evalutate (M*N*T*S)/(R*F*G*H), assuming these are all pre-initialized word variables.
mov ax, M imul N ;answer now in DX:AX idiv R ;now in AX imul T idiv F imul S idiv G ;now in AX, but remainder in DX mov DX, 0 ;clear DX idiv H ;final answer in AX
Quiz #4 (23 Jan)
LIST DW 10 DUP (?)
Assuming the 10 values in LIST have been initialized, write the code to add up the members of LIST with the result in ax. Use the loop instruction.
Here is one possible solution:
mov ax, 0 ;clear ax for addition mov bx, 0 ;use a base pointer for offset into array mov cx, 10 ;loop 10 times ADDING: add ax, LIST[bx] ;LIST[bx] is same as [LIST + bx] add bx, 2 ;move to next word loop ADDING ;sum now in ax
Quiz #3 (18 Jan)
NUM DW ?
For each, identify the type of the second operand:
MOV AX, BX ;register MOV AX, NUM ;direct (memory) MOV AX, 32H ;immediate (constant) MOV AX, "IC" ;immediate (constant) MOV AX, [BX] ;indirect (memory)
Quiz #2 (16 Jan)
Write the outline code of an assembler program.
.MODEL small .586 ; allows Pentium instructions to be used .STACK 100H .DATA ; put data definitions here .CODE MAIN PROC mov ax, @data ;(optional: load ds seg register) mov ds, ax ;... procedure code here mov ax, 4C00h ;(optional: quit to Dos at end) int 21h MAIN ENDP SUB1 PROC ;... a second procedure SUB1 ENDP END MAIN
Quiz #1b (11 Jan -- Speed Test) [1 point]
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 #1a (11 Jan) [2 points]
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