West Bengal Institute of Technology (WBIT) 2009 B.Tech Computer Science and Engineering Formal Language and Automata Theory - Question Paper
Formal Language and Automata Theory
CS401
Credits:4
2009
C8/B.Tech(CSE)/8EM-4/CS-401/08 3
ENGINEERING * MANAGEMENT EXAMINATIONS, JUNE-2009
FORMAL LANGUAGE & AUTOMATA THEORY
Time : 3 Hours J [ Full Marks : 70
: - . . ' .'r-:' ; : . . P
, GROUP-A
\ (Multiple Choice Typ OnMtkMM)
1. Choose the correct alternatives of the following : Id x 1 * 10
U 1,= { a" bn cn , where ne 1} Is
a) regular
b) contest free but not regular
c) context sensitive but not context free
d) none of these.
10 Which te true of the following ?
a) Merger graph is a directed graph
b) Compatible graph is a directed graph
c) Both are directed
d) None of these.
iii) Ihe Intersection of a CFL and regular language is
a) context free
b) r egular but not context free .
c) neither context free nor regular
d) both regular and context free.
iv) a* ( a + b) * is equivalent to
a) a* + b* b) (ab)*
i + b
c) a* b* dj None ofthese.
. ' v : N
CSTecli(CB)/U-4/C8-401/09
v) ' Which of the following productions is in CNF ?
a) S-> aA b) SA-> AS
c) S-*AB d) All of these.
vi) Context free language are not closed under a) union b) complementation c) concatenation ' d) star closure.
vii) Which is more suitable for an'Ambiguous Grammar 7
a) All ambiguities can be removed
b) Ambiguity can be removed by setting priority
' ' - . . . a* . . 1 .
c) Only inherent ambiguity can be removed
d) There is no suitable rule for removing ambiguity.
viii) Merger table is a substitute of
a) Merger graph b) Compatible graph
c) Minimized machine d) Finite state machine.
ix) DFA converted from an NFA with n states can have maximum
a) n states b) n! states
c) 2n states d) nC2 states.
x) The accepting automata for the context sensitive language is
a) linear bounded automata b) finite automata
c) push-down automata d) all of these.
/
C8/B.Tecb(CSE)/SEH-4/C8-401/09 5
GROUP - B ( Short Answer Type guestloiu )
Answer any three of the following.
3 x 5 = 15
produces the If it Is known 5
2. In response to an unknown Input sequence, the machine given below output sequence 1110000010. Find the Input sequence to the machine that Its initial state Is A and final state Is F.
|
PS |
ATS, z | |
|
X ll o |
x= 1 | |
|
A |
B, 1 |
C, 0 |
|
B |
D, 1 |
B, 1 |
|
C |
E. 1 |
B. 0 |
|
D |
A, 0 |
E. 0 |
|
E |
F, 0 |
D, 1 |
|
F |
D, 0 |
A, 1 |
3. What Is the basic difference between Mealy machine and Moore machine ? Construct
i
a Mealy machine which Is equivalent to the Moore machine given below : 2 + 3
|
PS |
NS |
2 | |
|
x 0 |
1 | ||
|
<Jo |
2 |
1 | |
|
9i |
3 |
32 |
0 |
|
<*2 |
<i2 |
1 | |
|
<*3 |
9o |
9s |
1 |
4. - Show that Li ( ap | p is prime } Is not regular. 5
C8/B.Tech(C8E)/8Bal-4/C8-401 /O
5. Let G bc the grammar S -> oB/ba. A -> a/aS/bAA. B -> b/bS/aBB. Tor the string aaabbabbba find a. 2 + 2+1
a) leftmost derivation
b) rightmost derivation
c) parse tree.
6 is the following machine Information lossless ? If yes. find the order of losslessness.
4 + 1
|
PS |
NS.z | |
|
x 0 |
x = 1 | |
|
A |
A. 0 |
B, 0 |
|
B |
C. 0 |
D, 0 |
|
C |
D, 1 |
C. 1 |
|
D |
B. 1 |
A. 1 |
GROUP -C (Long Answer Type Question* )
3 x 15 = 45 2
Answer any three of the following.
State the difference between DFA and NFA.
a)
b)
c)
d)
7.
Design an NFA which accepts set of all binary strings containing 1100 or 1010 as substrings.
What Is regular language ? '
Find regular expressions over I = { a, b} for the languages defined as follows :
I) LI = { am bm : m > 0 }
II) L2 = { a2n b2m* 1 | nSO, mriiO)
HI) L3 = {bmabn: m>0, n>0}
.8
| ||||||||||||||||||||||||||||||||||||||||||||||||||
|
d) Give definition of lossy and lossless machine. |
|
ft machine: | ||||
|
Present State |
Next State, o/p |
Next State, o/p | ||
|
Up - o |
t/p= 1 |
i/p = 2 |
i/p = 3 | |
|
A |
C, 1 |
E, 1 |
B, 1 | |
|
B |
E, 0 |
- |
- |
- |
|
C |
F, 0 |
' F 1 |
- |
- 1 |
|
D |
B, 1 |
- | ||
|
E |
F, 0 |
A, 0 |
D, - | |
|
F |
C, - |
, - |
B, 0 |
C, 1 |
Convert grammars to Grelbach Normal Form ( GNF).
I) S - aSa | aSb | e
2xl
11. a)
II) S - aSB | aSbS | e.
Find a reduced grammar equivalent to the grammar S -> aAa, A -> bBB, B -> ab, C-> aB.
b)
c)
Explain the concept of 2-way finite automata. 5 + 6 + 4
END
4401 ( 04/06 )
|
Attachment: |
| Earning: Approval pending. |
