Practice Test: Question Set - 01
1. Basic limitation of FSM is that it
- (A) Cannot
remember arbitrary large amount of information
- (B) Sometimes
fails to recognize grammars that are regular
- (C) Sometimes
recognizes grammars are not regular
- (D) None of
these
2. The language of all words with at least 2 a's can be described by the regular expression
- (A) (ab)*a and a
(ba)*
- (B) (a + b)* ab*
a (a + b)*
- (C) b* ab* a (a
+ b)*
- (D) All of these
3. Given A = (0,1) and L = A*. If R = (0n 1n, n > 0) , then language L ∪ R and R are respectively
- (A) Regular,
regular
- (B) Not regular,
regular
- (C) Regular, not
regular
- (D) Context
free, not regular
4. The following grammar
G = (N, T, P, S)
N = {S, A, B, C, D, E}
T = (a, b, c}
P : S ? ABCD
BCD ? DE
D ? aD
D ? a
E ? bE
E ? c is
5. The following CFG is in
- (A) Is type 3
- (B) Is type 2
but not type 3
- (C) Is type 1
but not type 2
- (D) Is type 0
but not type 1
5. The following CFG is in
S ? aBB
B ? bAA
A ? a
B ? b
6. In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of
7. Which of the following denotes Chomskian hiearchy?
8. The intersection of CFL and regular language
9. Consider a language L for which there exists a Turing machine TM, T, that accepts every word in L and either rejects or loops for every word not in L. The language L is
10. Which of the following statements is (are) correct?
Show and hide multiple DIV using JavaScript
View All Answers
Next Tests:
- (A) Chomsky
normal form but not strong Chomsky normal form
- (B) Weak Chomsky
normal form but not Chomsky normal form
- (C) Strong
Chomsky normal form
- (D) Greibach
normal form
6. In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of
- (A) Grammar
symbols on the right hand side
- (B) Terminals on
the right hand side
- (C) Non-terminals
on the right hand side
- (D) All of these
7. Which of the following denotes Chomskian hiearchy?
- (A) REG ? CFL ?
CSL ? type0
- (B) CFL ? REG ?
type0 ? CSL
- (C) CSL ? type0
? REG ? CFL
- (D) CSL ? CFL ?
REG ? type0
8. The intersection of CFL and regular language
- (A) Is always
regular
- (B) Is always
context free
- (C) Both (a) and
(b)
- (D) Need not be
regular
9. Consider a language L for which there exists a Turing machine TM, T, that accepts every word in L and either rejects or loops for every word not in L. The language L is
- (A) NP hard
- (B) NP
complete
- (C) Recursive
- (D) Recursively
enumerable
10. Which of the following statements is (are) correct?
- (A) Recursive
languages are closed under complementation
- (B) If a
language and its complement are both regular, the language is recursive
- (C) Set of
recursively enumerable language is closed under union
- (D) All of these
Next Tests:
Blogger Comment
Facebook Comment