West Bengal Institute of Technology (WBIT) 2009-5th Sem B.Tech Information Technology Formal Languaage & Automata Theory - University of Technology, , th. - Question Paper
Name
Roll No. :...........................................................................................................................
Invigilator's Signature :..................................................................................................
CS/B.Tech(IT)/SEM-5/CS-5i2/2009-i0
2009
FORMAL LANGUAGE & AUTOMATA THEORY
Time Alloted : 3 Hours Full Marks : 70
The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words
As far as practicable.
GROUP -A (Multiple Choice Type Questions)
1. Choose the correct alternatives for any ten of following : 10 x 1= 10
i) Let R1 and R2 be regular sets defined over alphabet X then
a) R1 fl R2 is not regular.
b) R1 U R2 is not regular.
c) X H R2 is not regular.
d) R2* is not regular.
ii) Which of the following strings can be obtained by the language L = { ai b2i/i> 1}?
a) aaabbbbbb b)aabbb
c) abbaabbbb d)aaaabb
iii) The regular expression with all strings of os and ls with atleast two consecutive os is
|
a) 1 + (10) * c) (0 + 1) * 011 iv) Which string can be generated by S aS / bA , A d / ccA ? a) aabccd c) abcca v) The regular sets are closed under a) Union c) Kleene closure vi) The intersection of CFL and regular language a) is always regular c) both (a) & (b) |
b) (0 +1) * 00 (0 +1) d) 0 * 0 * 1 * b) adabcca d) abababd. b) Concatenation d) all of these. b) is always context - free d) need not to be regular. |
vii) A grammar that produces more than one parse tree for some sentence is called
a) ambiguous b) unambiguous
c) regular d) none of these.
viii) Consider the regular expression ( o + 1) ( o + 1 ) .... n times. The minimum state finite automation that recognizes the language represented by this regular expression contains
b) n + 1 states d) n - 1 states.
a) n states c) n + 2 states
ix) The vernacular language English, if considered a formal language is a
a) regular language
b) context - free language
c) context - sensitive language
d) none of these.
x) Palindromes cannot be recognized by Finite State Machine because
a) an FSM cannot remember arbitrarily large amount of information
b) an FSM cannot fix the mid - point
c) FSM cannot find whether the second half of the string matches the first half
d) all of these.
xi) NDFA can be constructed equivalent of
a) type - 0 grammar b) type - 1 grammar
c) type - 2 grammar d) type - 3 grammar.
xii) Pumping lemma for CFG proves that a given language
a) belongs to CFG
b) does not belongs to CFG
c) belongs to regular grammar
d) none of these.
xiii) NDFA can be constructed equivalent of
a) only type - 1 grammar b) only type - 2 grammar
c) only type - 3 grammar d) all grammars.
xiv) If a machine of n states is p. definite, then
a) p. < n - 1 b) p. > n - 1
c) p. = n - 1 d) none of these.
|
xv) Merger table is substitute of a) merger graph c) minimized machine |
b) compatible graph d) finite state machine. |
xv) Merger table is substitute of
a) merger graph b) compatible graph
c) minimized machine d) finite state machine.
xvi) If G = ( { S }, { a }, { S SS}, S ), the language generated by G is
a) L ( G ) = 0 b) L ( G ) = an
c) L ( G ) = a0 d) L ( G ) = an ban.
GROUP -B (Short Answer Type Questions)
Answer any three of the following: 3 x 5 = 15
2. Test the machine below is definiteness or not. If yes, find the order 5
|
PS |
NS | |
|
x = 0 |
x = 1 | |
|
A |
A |
B |
|
B |
E |
B |
|
C |
E |
F |
|
D |
E |
F |
|
E |
A |
D |
|
F |
E |
B |
3. a) State pumping lemma for Context Free Language.
b) Using this lemma prove that L = { ai b | j = i2} is not Context Free Language.
4. a) What is ambiguous grammar ?
b) Check whether the following grammar is ambiguous :
S iCtS | iCtSeS | a
C b 1 + 4
5. a) What are the differences between Moore machine and Mealy machines?
b) Construct a Moore machine equivalent to the Mealy machine :
|
PS |
NS | |||
|
a = 0 |
a = 1 | |||
|
NS |
o/p |
NS |
o/p | |
|
q1 |
q1 |
1 |
q2 |
0 |
|
q2 |
q4 |
1 |
q4 |
1 |
|
q3 |
q2 |
1 |
q3 |
1 |
|
q4 |
q4 |
0 |
q1 |
1 |
2 + 3
6. aa) What are the differences between DFA & NFA? bb) Construct DFA which is equivalent to given NFA.
M = ( { q0, q1, q2, q3 }, { 0, 1 }, 8, q0, { q3 } ) and 8 is given in the table :
|
Q / 2 |
0 |
1 |
|
q0 |
q0, q1 |
q0 |
|
Q1 |
Q2 |
q1 |
|
q2 |
q.3 |
q.3 |
|
q3 |
q2 |
2 + 3
GROUP -C (Long Answer Type Questions)
Answer any three of the following: 3 x 15 = 45
7. a) State and prove Ardens Theorem.
b) Prove that ( 1 + 00* 1) + (1 + 00* 1 ) ( 0 + 10* 1) * ( 0 + 10* 1) = 0*1 ( 0 + 10* 1)*
c) Find the regular expression for the given transition diagram :
a a
 |
|
b |
5 + 5 + 5
8. a) What is PDA?
b) Design a PDA to accept the following language L = ( R | (0, 1)*).
c) Construct a context free grammar generating following language :
L = { an bn |n > 1 } U {am b2m |m > 1 } and also construct PDA for the above derived CFG. 1 + 6 + 8
9. a)
|
PS |
NS, z | ||
|
I1 |
I2 |
I3 | |
|
A |
C, 0 |
E, 1 | |
|
B |
C, 0 |
E,-- | |
|
C |
B,-- |
C, 0 |
A,-- |
|
D |
B,0 |
C,-- |
E,-- |
|
E |
E |
A,-- | |
For the incompletely specified machine shown above, find a minimum state reduced machine containing the original one.
|
PS |
NS, z | |
|
x = 0 |
x = 1 | |
|
A |
B,1 |
H, 1 |
|
B |
F, 1 |
D, 1 |
|
C |
D, 0 |
E, 1 |
|
D |
C, 0 |
F, 1 |
|
E |
D, 1 |
C, 1 |
|
F |
C, 1 |
C, 1 |
|
G |
C, 1 |
D, 1 |
|
H |
C, 0 |
A, 1 |
Using this table
i) find the equivalence partition.
ii) find the standard form of the corresponding reduced machine.
What the minimum length sequence that distinguishes state A from state B.
8 + (3 + 3 +1 )
10. a) For the grammar SaB|bA A a | aS | bAA B b | bS |aBB
Give the left most and right most derivation for the string aaabbabbba.
b) Design a CFG for the language
L (G ) = { 0n 1m | n * m }
c) Construct a regular grammar G generating the regular set by r = 01 ( 0 + 1 )*
11. a) Remove left recursion from guven grammar :
A Ba |b B Bc | Ad | e
b) Convert the grammar into GNF :
S a ABb | a A aaA |B B bAb
c) In response to an unknown input sequence, the machine given below produces the output sequence 1110000010. Find the input sequence to the machine if it is known that is initial state is A and final state is F.
|
PS |
NS, z | |
|
x = 0 |
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 |
|
Attachment: |
| Earning: Approval pending. |
