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
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:
Blogger Comment
Facebook Comment