Discrete Structures Exam 2
Give a production grammar for the language L = {x | x ∈ (a,v)*, the number of a's in x is
a multiple of 3} - ANS-S -> bS | b | aA | bA
A -> aB
B -> bB
B -> aS
The production grammar {S -> aSbb | abb} is - ANS-Type 2 grammar
Which string can be produced by S->aS | bA, A->d | ccA?
a)aabccd
b)adabcca
c)abcca
d)abababd - ANS-a)aabccd
Which of the following statements is wrong?
a) The regular sets are closed under intersection
b) The class of regular sets is closed under substitution
C) The class of regular sets is closed under homomorphism
d)Context Sensitive Grammar(CSG) can be recognized by FSM - ANS-d
The Union of CFL and regular languages
a) is always regular
b) is always context free
c) both a and b
d) need not be regular - ANS-c
Which of the following is undecidable?
a) Membership problem of CFG
b) ambiguity problem for CFG
c)Finiteness problem for FSA
d)Equivalence problem for FSA - ANS-b
Pushdown Automata represents a
a) type 0 grammar
b) type 1 grammar
c) type 2 grammar
d) type 3 grammar - ANS-c
, If every string of a language can be determined whether it is legal or illegal in finite time
the language is called
a) Decidable
b) undecideable
c) Interpretive
d) non deterministic - ANS-a
A context free language can be recognized by
a) Finite State Automaton
b) Linear Bound Automaton
c) Pushdown Automaton
d) both B and C - ANS-d
Which of the following is the most general phase structured grammar?
a) Regular
b) Context sensitive
c) Context free
d) None of the above - ANS-b
The following grammar
S->bS | b
is a
a) type-3 grammar
b) type-2 grammar
c) type-1 grammar
d) type-0 grammar - ANS-a
All strings having equal number of a and b can be recognized by
a) DFA
b) NDFA
c) PDA
d) All of the above - ANS-c
Which of the following statements is false?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure - ANS-c
Give a production grammar for the language L = {x | x ∈ (a,v)*, the number of a's in x is
a multiple of 3} - ANS-S -> bS | b | aA | bA
A -> aB
B -> bB
B -> aS
The production grammar {S -> aSbb | abb} is - ANS-Type 2 grammar
Which string can be produced by S->aS | bA, A->d | ccA?
a)aabccd
b)adabcca
c)abcca
d)abababd - ANS-a)aabccd
Which of the following statements is wrong?
a) The regular sets are closed under intersection
b) The class of regular sets is closed under substitution
C) The class of regular sets is closed under homomorphism
d)Context Sensitive Grammar(CSG) can be recognized by FSM - ANS-d
The Union of CFL and regular languages
a) is always regular
b) is always context free
c) both a and b
d) need not be regular - ANS-c
Which of the following is undecidable?
a) Membership problem of CFG
b) ambiguity problem for CFG
c)Finiteness problem for FSA
d)Equivalence problem for FSA - ANS-b
Pushdown Automata represents a
a) type 0 grammar
b) type 1 grammar
c) type 2 grammar
d) type 3 grammar - ANS-c
, If every string of a language can be determined whether it is legal or illegal in finite time
the language is called
a) Decidable
b) undecideable
c) Interpretive
d) non deterministic - ANS-a
A context free language can be recognized by
a) Finite State Automaton
b) Linear Bound Automaton
c) Pushdown Automaton
d) both B and C - ANS-d
Which of the following is the most general phase structured grammar?
a) Regular
b) Context sensitive
c) Context free
d) None of the above - ANS-b
The following grammar
S->bS | b
is a
a) type-3 grammar
b) type-2 grammar
c) type-1 grammar
d) type-0 grammar - ANS-a
All strings having equal number of a and b can be recognized by
a) DFA
b) NDFA
c) PDA
d) All of the above - ANS-c
Which of the following statements is false?
a) Context-free languages are closed under union
b) Context-free languages are closed under concatenation
c) Context-free languages are closed under intersection
d) Context-free languages are closed under Kleene closure - ANS-c
