Indian Institute of Technology Madras (IIT-M) 2000 A.M.I.E.T.E Computer Science

R1 and R2 is described as u
R2J R1
(a) Every vertex in G has the identical degree. What is the degree of a vertex in G?
(b) How many connected components does G have?
3. (a) Construct as minimal finite state machine that accepts the language, over {0,1}, of all
strings that contain neither the substring 00 nor the substring
11.
(b) Consider the grammar
aSAb
A- bA
A- C
Where 5, A are non-terminal symbols with S being the begin symbol; a,b are terminal symbols
and c is the empty string. This grammar generates strings of the form a’bfor a few i, j 0,
where i and j satisfy a few condition. What is the condition on the values of i and j?
4. A pushdown automaton (pda) is provided in the subsequent extended notation of finite state
diagrams:
_______ 2.s/s
1.s/1.s 1,1.s/s
The nodes denote the states while the edges denote the moves of the pda. The edge tags
are of the form d, s/s’where d is the input symbol learn and s,s’are the stack contents before
and after the move. For example the edge tagged 1, s/1.s denotes the move from state q0 to
q0in which the input symbol one is learn and pushed to the stack.
(a) Introduce 2 edges with improper tags in the above diagram so that the resulting pda
accepts the language
{x2xR x E {0, 1} *, xR denotes revese of x}, by empty stack.
(b) define a non-deterministic pda with 3 states in the above notation that accept the
language {o1m fl < m < 2n) by empty stack
4. Design a logic circuit to convert a single digit BCD number to the number modulo 6 as
follows (Do not detect illegal input):
(a) Write the truth table for all bits. tag the input bits I, 1, .... With I as the lowest significant
bit. tag the output bits R1, R2, .... With R1 as the lowest significant bit. Use one to signify truth.
(b) Draw 1 circuit for every output bit using, altogether, 2 two-input AND gates, 1 twoinput
gate and 2 NOT gates.
5. Consider the 8085 instruction IN 09H stored as follows:
And the subsequent incomplete timing diagram for the instruction:
T1 T2 T3 T4 T5 T6 T7 T8 T9 TA
A15-A8
AD7 C>
IO/M
(a) Write the contents of the boxes, A, B, C and D in hexadecimal in your ans sheet. Do
not draw any pictures.
(b) Write the state of both ALE and RD pins at time units Ti, T2, T3 and T4.
(c) How do you generate the signal that tells the peripheral to put the data on the bus?

Earning:   Approval pending.