# Recent questions tagged unsolved

1
Consider the DFA $M$ and NFA M2 as defined below. Let the language accepted by machine $M$ be $L$. What language machine M2 accepts, if $F2=A$ ? $F2=B$ ? $F2=C$ ? $F2=D$ ? $M=(Q, \Sigma, \delta, q_0, F)$ $M2=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p \in Q; q \in F\}$
2
Consider the following grammar: $S \rightarrow S$ $S \rightarrow SS \mid a \mid \epsilon$ Indicate the shift-reduce and reduce-reduce conflict (if any) in the various states of the LR(0) parser.
1 vote
3
The code for the implementation of a sub-routine to convert positive numeric data from binary to appropriate character string in a $PDP-11$ like machine has been given below Note-that $SP$ is the stack pointer and $R_i$ represents $i^{th}$ ...
4
A ROM has the following time parameters: Maximum Address to valid Data Output delay = 30 n sec. Maximum Chip Select to valid Data Output delay = 20 n sec. Maximum Data Hold time (after address change or after chip deselect) = 10 n sec Assume that, the chip ... time is negligible What is the maximum rate at which a CPU can continuously read data from this ROM? (Show your calculations step-by-step)
5
An $8-bit$ data path is to be set up using two $4-bit$ ALU's and suitable multiplexers. The ALU's accept two operands $A$ and $B$ on which a total of $16$ operations can be performed. The operand $A$ is from one of two register-arrays each ... placed on a bus. List the data path control signals, and estimate the minimum width of a signal microcode word needed for the generation of these signals.
6
A modern day machine typically has an atomic TEST AND SET instruction. Why?
7
State any undesirable characteristic of the following criteria for measuring performance of an operating system: Waiting time
8
State any undesirable characteristic of the following criteria for measuring performance of an operating system: Turn around time
9
Consider the following grammar for variable declarations: <vardecl> $\rightarrow$ <vardecl><idlist> : <type>; <vardecl> $\rightarrow \in$ <idlist> $\rightarrow$ <idlist>, id <idlist> $\rightarrow$ id <type> $\rightarrow$ integer <type> ... error messages wherever necessary. Make suitable assumptions regarding procedures operating on the symbol table; you need not elaborate upon these procedures.
10
In a certain computer system, there is special instruction implemented to call subroutines. The instruction is JSR Reg.Sub Microsequence: Temp ← Sub SP ← (SP)+2 (SP) ← (Reg) Reg ← (PC) PC ← (Temp) Where Temp is an internal CPU register Sub is calling ... you would implement co-routine using the JSR instruction. Show the control flow diagram and the contents of the stack before and after the call.
11
A certain computer system was designed with cache memory of size $1$ Kbytes and main memory size of $256$ Kbytes. The cache implementation was fully associative cache with $4$ bytes per block. The CPU memory data path was $16$ ... Answer the following questions: What is the hit ratio? Suggest a change in the program size of model to improve the hit ratio significantly.
12
It is required to implement a stack using bidirectional shift registers providing stack under flow and overflow detection capability. How many shift registers are needed for a stack capacity of $n$ $k-$bit words? Show the schematic diagram of the implementation, clearly indicating all the data and control lines.
13
Provide short answers to the following questions: Express the following list in terms of a linked list structure suitable for internal representation. $(((ab)c)d((e)))$
14
Provide short answers to the following questions: Consider the definition of macro B, nested within the definition of a macro A. Can a call to macro B also appear within macro A? If not, why not? If yes, explain if there are any restrictions.
15
Consider the grammar: $G_{2}$: Para $\rightarrow$ Sentence RP/Sentence RP $\rightarrow$ b Sentence RP | b Sentence Sentence $\rightarrow$ Word b Sentence| Word Word $\rightarrow$ letter *word | letter letter $\rightarrow$ id Where $id,,*,.b$ ar terminals Convert ... show how to use a stack algorithm to parse the following string$id*id.b id * id.$ The parse should generate a rightmost derivation.
1 vote
16
The following algorithm (written in pseudo-pascal) work on an undirected graph G program Explore (G) procedure Visit (u) begin if Adj (u) is not empty {comment:Adj (u) is the list of edges incident to u} then begin Select an edge from Adj (u); Let edge ... edges, given that each vertex can be accessed and removed from LIST in constant time. Also show that all edges of the graph are traversed.
17
Consider the following instance of the $0 -1$ Knapsack problem: $\max 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ Subject to $4X_{1} + 8X_{2} + 12X_{3} + 16X_{4} + 20 X_{5} < 32$ and $X_{i}=0$ or $1$ for $i=1,\dots,5$. ... . Number the nodes in the tree in the order in which they are expanded and for each node show the bound on the partial solutions and the decision which leads to that node.
1 vote
18
Assume that an instruction test-and-set (TS) has been provided in a machine whose function is as follows: 'the left most bit of the one byte operand is checked and accordingly the condition code (CC) is set to $1$ or $0$. After checking and setting the condition code, implement a critical region using this instruction.
19
Design an $8 \times 8$ multiplier using five 4-bits adders and 4 ROM's each programmed to realise $4 \times 4$ multiplier.
1 vote
20
The above circuit produces the output sequence: 1111 1111 0000 0000 1111 0000 1111 000 1111 0001 0011 010 1010 1010 1010 1010
21
It is required to design a hardwired controller to handle the fetch cycle of a single address CPU with a $16$ bit instruction-length. The effective address of an indexed instruction should be derived in the fetch cycle itself. Assume that the lower order $8$ bits of an instruction constitute the operand field. Draw the logic schematic of the hardwired controller including the data path.
22
Show the activation records and the display structure just after the procedures called at lines marked $x$ and $y$ have started their execution. Be sure to indicate which of the two procedures named $A$ you are referring to. Program Test; Procedure A; Procedure B; Procedure A; begin …… end A; begin y: A; end B; begin B; end A; begin x: A; end Test
23
Three devices $A, B$ and $C$ are connected to the bus of a computer, input/output transfers for all three devices use interrupt control. Three interrupt request lines INTR1, INTR2 and INTR3 are available with priority of INTR1 > priority of INTR2 > priority of INTR3. Draw a ... of the priority logic, using an interrupt mask register, in which Priority of $A$ > Priority of $B$ > Priority of $C.$
24
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
25
Suppose we have a computer with single register and only three instructions given below: ... T \rightarrow (E)\mid id$}\\ \end{array}$ Write a syntax directed translation to generate code using this grammar for the computer described above.
26
The language $L,$ defined by the following grammar, allows use of real or integer data in expressions and assignment statements. <assign-stmt> :: <LHS> := <E> <E> ::= <E> + <T>|<T> <T> ::= <T> * <V>|<V> <V> ::= id|(<E>) (LHS) :: ... the postfix form. You may assume that the name and type of variable can be obtained by making the function calls' give_name $(id)$ and give_type $(id)$ respectively.
27
Suppose we have a function HALTS which when applied to any arbitrary function $f$ and its arguments will say TRUE if function $f$ terminates for those arguments and FALSE otherwise. Example: Given the following function definition. FACTORIAL (N) = IF (N=0) ... not possible to have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.
We wish to construct a $B^+$ tree with fan-out (the number of pointers per node) equal to $3$ for the following set of key values: $80, 50, 10, 70, 30, 100, 90$ Assume that the tree is initially empty and the values are added in the order given. Show ... Intermediate trees need not be shown. The key values $30$ and $10$ are now deleted from the tree in that order show the tree after each deletion.
It is required to design a hardwired controller to handle the fetch cycle of a single address CPU with a $16$ bit instruction-length. The effective address of an indexed instruction should be derived in the fetch cycle itself. Assume that the lower order $8$ bits of an instruction constitute the operand field. Give the register transfer sequence for realizing the above instruction fetch cycle.
Using D flip-flop gates, design a parallel-in/serial-out shift register that shifts data from left to right with the following input lines: Clock $\text{CLK}$ Three parallel data inputs $A, B, C$ Serial input $S$ Control input $\text{load} / \overline{\text{SHIFT}}$.