1. Let R1 and R2 be regular sets defined over alphabet ∑ then
a) R1 ∪ R2 is regular
b) R1 ∩ R2 is regular
c) ∑ ∩ R2 is not regular
d) R*2 is not regular
2. Consider the production of the grammar
S → AA
A → aa
A → bb
Describe the language specified by the production grammar.
a) L = {aaaa, aabb, bbaa, bbbb}
b) L = {abab, abaa, aaab, baaa}
c) L = {aaab, baba, bbaa, bbbb}
d) L = {aaaa, abab, bbaa, aaab}
3. Given a production grammar that specified language
L = {a ͥ b² ͥ / i ≥ 1}
a) {S → aSbb, S → abb}
b) {S → aSb, S → b}
c) {S → aA, S → b, A → b}
d) None of these
4. Which of the following string can be obtained by language
L = {a ͥ b² ͥ / i ≥ 1}
a) aaabbbbbb
b) aabbb
c) abbabbba
d) aaaabbbabb
5. Given a production grammar for the language L = {x/x ∈ (a, b)* , the number of a’s in x is a multiple of 3}
a) {S → bS, S → b, S → aA, S → bA, A → aB, B → bB, B → aS, S → a}
b) {S → aS, S → bA, A → bB, B → bBa, B → bB}
c) {S → aaS, S → bbA, A → bB, B → ba}
d) None of these
6. Let L1 = {aꜞ bʲ / i, j ≥ 1, i≠ j} and L2 = {aꜞ bʲ / i < j}, the union of L1 and L2 is given by
a) {aꜞ bʲ / i > j ≥ 1}
b) {aꜞ bʲ / i, j ≥ 1}
c) {aꜞ bʲ / i > j ≥ 1}
d) {aꜞ bʲ / i, j ≥ 1, i≠ j}
7. Given a production grammar for the language
L = {aꜞ bʲ / i, j ≥ 1, i≠ j}
a) {S → aS, S → aB, B → ab, A → aaB, B → b}
b) {S → A, S → C, A → aA, A → aB, B → aBb, B → ab, C → Cb, C → Bb}
c) {S → A, A → aA, A → aB, B → ab}
d) None of these
8. The production grammar is (S → aSbb, S → abb) is
a) Type-3 grammar
b) Type -2 grammar
c) Type -1 grammar
d) Type -0 grammar
9. Which of the following statement is wrong?
a) A turing machine cannot solve halting problem
b) Set of recursively enumerable language is closed under union
c) A finite state machine with 3 stacks is more powerful than finite state machine with 2 stacks
d) Context sensitive grammar can be recognized by a linearly bounded memory machine
10. Which of the following statement is wrong?
a) Recursive languages are closed under union
b) Recursive languages are closed under complementation
c) If a language and its complement are both regular, then the language must be recursive
d) A language is accepted by FA if and only if it is recursive