Practice Test: Question Set - 05
1. L = (an bn an | n = 1,2,3) is an example of a language that is
- (A) Context free
- (B) Not context
free
- (C) Not context
free but whose complement is CF
- (D) Both (b) and
(c)
2. The set of all strings over the alphabet S = {a, b} (including e) is denoted by
- (A) (a + b)*
- (B) (a + b)+
- (C) a+b+
- (D) a*b*
3. Which of the following strings is not generated by the following grammar? S ? SaSbS|e
- (A) aabb
- (B) abab
- (C) aababb
- (D) aaabb
4. If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
- (A) L1 L2
- (B) L1
∩ L2
- (C) L1 ∩ R
- (D) L1 ∪ L2
5. Which of the following regular expression identity is true?
- (A) r(*) = r*
- (B) (r*s*)* = (r
+ s)*
- (C) (r + s)* =
r* + s*
- (D) r*s* = r* +
s*
6. The logic of pumping lemma is a good example of
- (A) Pigeon-hole
principle
- (B) Divide-and-conquer
technique
- (C) Recursion
- (D) Iteration
7. Consider a grammar :
G = ( { x , y ) , { s , x , y } , p , s)
where elements of parse :
S--> x y
S -->y x
x--> x z
x--> x
y--> y
z--> z
The language L generated by G most accurately is called
- (A) Chomsky type
0
- (B) Chomsky type
1
- (C) Chomsky type
2
- (D) Chomsky type
3
8. Consider the following CFG
S ? aB S ? bA
B ? b A ? a B ? bS A ? aS
B ? aBB A ? bAA
Consider the following derivation
S ? aB ? aaBB
? aaBb
? aabSb
? aabbAb
? aabbab
9. Context-free grammar can be recognized by
10. What is the highest type number which can be applied to the following grammar?
Show and hide multiple DIV using JavaScript
View All Answers
Next Tests:
This derivation is
- (A) A leftmost
derivation
- (B) A rightmost
derivation
- (C) Both
leftmost and rightmost derivation
- (D) Neither
leftmost nor rightmost derivation
9. Context-free grammar can be recognized by
- (A) Finite state
automation
- (B) 2-way linear
bounded automata
- (C) Push down
automata
- (D) Both (b) and
(c)
10. What is the highest type number which can be applied to the following grammar?
S —> Aa, A —> Ba, B —> abc
- (A) Type 0
- (B) Type 1
- (C) Type 2
- (D) Type 3
Next Tests: