West Bengal Institute of Technology (WBIT) 2008-4th Sem B.Tech Computer Science and Engineering Computer Science - Formal Language and Automata Theory - Question Paper
C8/B.TBCH (CU)/SBlf-4/CS-401/06 3
ENGINEERING & MANAGEMENT EXAMINATIONS, JUNE - 2008 FORMAL LANGUAGE AND AUTOMATA THEORY SEMESTER-4
Time: 3 Hours] [ Full Marks : 7C
GROUP-A (Multiple Choice Type Questions) .
1. Choose the correct alternatives for the following : 10x1 = 1C
. _
I) Which of the following regular egressions over { 0, 1 } denotes the set of all strings not containing 100 as a sub-string?
a) 0*(1*0)* b) 0*1010*
c) 0*1*01* d) 0*(10+1) *.
II) DFA has
a) single final state '
b) more than one Initial states
* c) . unique path (for a set of Inputs ) to the final state
d) all of these.
* . ill) Which of the following Is regular ?
a) Strings of 0's whose length is a perfect square
b) Strings of all palindromes made up of 0's & l 's
c) Strings of 0's, whose length is a prime number
d) Strings of odd number of zeroes,
iv) The logic of pumping lemma is a good example of
a) the pigeon-hole principle b) the divide & conquer technique
j ' .
c) recursion d) iteration.
. . . \
C8/B.TBCH (C8E)/8BM-/CS-01/08 4
v) The class of context free language Is not closed under
a) concatenation b) mnn
c) intersection d) repeated concatenation. I_I
vi) The grammar Q * ({S}, {0,1}, P,S) where P={S0S1, SOS, S-*S1, S-i-0} is a ' a) recursively enumerable language
b) regular language
c) context sensitive language
d) context free language. _
vli) If S is the number of states in NDFA then equivalent DFA can have maximum of
a) S states b) S-l state
c) 2s states d) 2s -1 states. 1
viii) If LI is the set of languages Accepted by a NPDA and L2 is the set of context free languages, then
a) L1=L2 b) L1CL2
c) L2QL1 d) None of these. 1 I
ix) What is the hipest type number to the grammar given by the following production rules
S -* Aa, A -* c | Ba, B-*abc
a) zero b) one
c) two d) three. . , _i_
x) Given an arbitrary NDFA with n states, the maximum number of states in an equivalent minimized DFA is at least
. ' * .
a) n * b) 2
c) n ! d) None of these. 1......J
(Short Answer Type Question* )
3 x 5 = *15
Answer any three of the following.
2. a) What do you mean by a subtree of a derivation tree ?
q _AS/a A - SbA/SS/ba. Show that
b) Consider O whose production, are S - aAS/a, A
s_ aabbaa by construct a dertvatton tree, by right most derivation, whose
2 + 3
yield is aabbaa. .
Next State |
i/p=0 |
Next state |
1 i/p=l 1 -1 | |
Present State |
State |
Ootpitt |
State |
! Output | |
Qi |
Q* |
1 ' 1 |
Q* |
0 |
Qa |
q3 |
0 |
Q4 |
1 |
- Qs * |
Qi |
0 |
Q4 |
0 |
Q4 |
q3 |
* . 1 |
q2 |
1 |
Reduce the following grammars to GNF : S - AO. A - OB. B - OA. B - 1
4.
5.
The set L a ,aVc /where i. * are integer and i.k ,1). Is L regular 7 Justly your
, answer.
CS/B.TBCH (C8E)/8EM-4/CS-U>l /OS 6 .
6. Minimize the following machine by determining the set of equivalent states.
Present State |
Next State |
i/p=o |
Next state |
i/p=l |
State |
Output |
State |
Output | |
A |
E |
1 |
C |
0 |
B |
C |
0 |
A |
0 |
C |
B |
0 |
G |
0 |
D |
G |
0 |
A |
0 |
E |
F |
1 \ |
B |
0 |
F |
E |
1 |
D |
0 |
O |
D |
0 |
G |
0 |
- H |
F |
. 1 |
B |
-o |
- GROUP-C
(Long Answer Type Question* )
Answer any three of the following questions. 3 x 15 = 45
7. a) State & discuss Myhill-Nerode theorem. 5
b) Write the CFG for the language
. L { 0* 1J 2k | iJ or Jk). . 5
c) Prove that CFLs are not closed under intersection and complement operation. 5
/)
/yCS/B.TKCH (CSE)/MtM-*/C8-401/0>
8 a} E _ E+E | E*E|a. Prove that the CFG with this production rule Is ambiguous.
* 2 + 3
Remove the ambiguity from this grammar.
b) S - AB; A - a. B - C/b, C - D; D - E, E - a. remove the unit production.
L = {a" bn | n * 0 }. Find a CFG to generate L2. 3 + 2
c) Design a PDA which accepts the language.
5
L * { W t (a,b)* 1IV has equal no. of a & b}.
9. a) A long sequence of input pulses enters a two-input, two-output synchronous sequential circuit, which Is required to produce an output pulse Z=l. whenever a
sequence 010101 occurs. Overlapping sequences are accepted. Draw the state
. 6 transition diagram.
b) Find minimum state reduced machine containing the following incompletely
9
specified machine.
irv-&446n fian
PS |
Ii |
NZ, Z U |
Is |
A |
C. 0 |
E. 1 |
- |
B |
C. 0 |
E,- |
- |
C |
B,- |
C, 0 |
A,- |
D |
B. 0 |
C,- |
E,- |
E |
E, 0 |
A.- |
/
CS/B.TECH [CSBJ/BBH-t/CS-401 /OS 8 ! Ilffflil ! PS |
x=0 |
, NZ.Z x=l |
A |
C, 0 |
D, 1 |
B |
D, 0 |
C. 1 |
C |
A, 0 |
B. 0 |
D |
C, 1 |
D, 1 |
Also find its order of information losslessness. 7
b) Find the minimal Inverse machine of the FSM in problem ( a ). 8
11. a) What do you mean by Inverse machine ? Write the definition of a lossless
* machine. What do you mean,by Halting problem of a Turing machine ? Why a
Turing machine is called linear bounded Automata ? 2 + 2 + 2 + 2
b) Consider the Turing machine's description is given in table below. Draw the computation sequence of the input string 00. 7 | ||||||||||||||||||||||||
|
END
I1V-2448111D0
Attachment: |
Earning: Approval pending. |