Instructions For The Section. Like: Part-A: Answer All The Questions: (20 0.5 10)

INSTRUCTIONS FOR THE SECTION.
Like: Total No of Questions in Section Number

to be
Part-A: Answer All the Questions: answered
(20*0.5=10)
1 PDA has ____ variants 0.5
a)DPDA,NPDA
b)CPDA,DPDA
c)DPAD,NPAD
d)CAD,CAP
2 CYK Stands for______ 0.5
a) Cocke–Young–Kasami
b) Cocke–Younger–Kasami
c) Cocke–Yoger–Kasami
d) Cocke–Yer–Kasami
3 CNF format is 0.5
a)NN N and NTERMINAL
b) NN N N and NTERMINAL
c) NN and NTERMINAL
d) N TERMINAL TERMINAL and
NTERMINAL
4 A CFG is ambiguous if 0.5
a) It has more than one rightmost derivations
b) It has more than one leftmost derivations
c) No parse tree can be generated for the CFG
d) None of the mentioned
5 Consider the grammar : 0.5
S —> ABCc | Abc
BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa
Which of the following sentences can be derived
by this grammar
a)abc
b)aab
c)aacc
d)aaccbb
6 The language of all words with at least 2 a's can 0.5
be described by the regular expression
a)All Options B,C and D correct
b)(ab)*a and a (ba)*
c)(a + b)* ab* a (a + b)*
d)b* ab* a (a + b)*
7 Any string of terminals that can be generated by 0.5
the following CFG is
S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a
a)has atleast two a's
1
b)has atleast one 'b'
c)should end in a 'a'
d)has no consecutive a's or b's
8 The DFA shown below accepts the set of all 0.5
strings over {0, 1} that
a)End with 00
b)End with 0
c)Begin either with 0 or 1
d)Contain the substring 00
9 CNF format is 0.5
NONTERMINAL-->NON TERMINAL NON
TERMINAL | TERMINAL
NONTERMINAL-->TERMINAL NON
TERMINAL | TERMINAL
NONTERMINAL-->NONTERMINAL
TERMINAL | TERMINAL
NONTERMINAL-->TERMINAL TERMINAL |
TERMINAL
10 Which among the following looks similar to the 0.5
given expression?
((0+1). (0+1)) *
{xϵ {0,1} *|x is all binary number with even
length}
{xϵ {0,1} |x is all binary number with even
length}
{xϵ {0,1} *|x is all binary number with odd
length}
{xϵ {0,1} |x is all binary number with odd
length}
11 Chomsky Hierarchy has ______ Number of 0.5
Languages
a)4
b)3
c)2
d)1
12 Context Sensitive Grammar have _________ 0.5
property
a)| β | <= | α |
b)| β | >= | α |
c)| β | > |αγ |
d)|γβ | <= | α |
13 There are ________ tuples in finite state 0.5
machine.
a)5
b)4
c)6
d)Unlimited
14 Which of the following statement is false? 0.5
a)In derivation tree, the label of each leaf node is

terminal
2
b)In derivation tree, the label of all nodes except
leaf nodes is a variable
c)In derivation tree, if the root of a sub tree is X
then it is called –tree
d)None of the mentioned
15 Here is a grammar G: 0.5
S → AB
A → 0A1 | 2
B → 1B | 3A .
which of the following strings are accepted by
Grammar
a)021300211
b)022111300211
c)None of the mentioned
d)Both of the mentioned
16 The grammar 0.5
S → SS | 0S1 | 1S0 | ɛ
Generates _______________ String
a)Equal number of 0’s and 1’s

b)Unequal number of 0’s and 1’s
c)Number of 0’s followed by any number of 1’s
d)None of the mentioned
17 Which finite automata easy to construct 0.5
a)NFA
b)DFA
c)PDA
d)TURING MACHINE
18 Which formula is required to convert NFA to 0.5
DFA
a)δ((q0,q1,q2.....qn),a)=δ(q0,a) U δ(q1,a) U
δ(q2,a)......U δ(qn,a)
b)µ((q0,q1,q2.....qn),a)=µ(q0,a) U µ(q1,a) U
µ(q2,a)......U µ(qn,a)
c)β((q0,q1,q2.....qn),a)=β(q0,a) U β(q1,a) U
β(q2,a)......U β(qn,a)
d)β((q0,q1,q2.....qn),a)=β(q0,a) U β(q1,a) U
µ(q2,a)......U µ(qn,a)
19 Which of the following input string is accepted 0.5
by given automata
a)0031275
b)2036920
c)1036910
d)1212121
20 S → aAa 0.5
A → bB
B → bB
3
B→c
This grammar is
a)Type-2 and Type-0

b)Type-3 but not Type-2
c)Type-1
d)Type-1 but not Type-3
Part-B: Answer any FIVE Questions: 7 5

(5*4=20)
1 Define Alphabet, Language, grammar, production rules , 4
derivation and derivation tree.
2 Explain Chomsky hierarchy of languages. With neat sketch 4
3 A Explain the process of converting NFA into DFA 2
3 B Convert given NFA into DFA 2
4 A Convert given regular expression into Finite Automata 2

Re=(a+b)c*d*
4 B Explain Closure and decision properties of regular sets 2
5 Show the CYK Algorithm with the following : – CNF grammar G 4

S  AB | BC
A  BA | a
B  CC | b
C  AB | a
w is ababa
Identify whether given w Is ababa in L(G)?
6 A Explain the differences between PDA and Finite Automata 1
6 B Design PDA for the language L={anbn|n>=1} 3
7 A Explain Linear Bounded Automata with example 1.5
7 B Design Turing Machine to accept even length palindrome 2.5

strings over and alphabet ∑={a,b}

Instructions For The Section. Like: Part-A: Answer All The Questions: (20 0.5 10)

Uploaded by

Copyright:

Available Formats

Instructions For The Section. Like: Part-A: Answer All The Questions: (20 0.5 10)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Instructions For The Section. Like: Part-A: Answer All The Questions: (20 0.5 10)

Uploaded by

Copyright:

Available Formats

INSTRUCTIONS FOR THE SECTION.

Like: Total No of Questions in Section Number

a)In derivation tree, the label of each leaf node is

a)Equal number of 0’s and 1’s

a)Type-2 and Type-0

Part-B: Answer any FIVE Questions: 7 5

3 A Explain the process of converting NFA into DFA 2

3 B Convert given NFA into DFA 2

4 A Convert given regular expression into Finite Automata 2

5 Show the CYK Algorithm with the following : – CNF grammar G 4

6 B Design PDA for the language L={anbn|n>=1} 3

7 A Explain Linear Bounded Automata with example 1.5

7 B Design Turing Machine to accept even length palindrome 2.5

You might also like