Theory of Computation MCQs with Answers - Set 04 - ObjectiveBooks

Practice Test: Question Set - 04

1. The defining language for developing a formalism in which language definitions can be stated, is called
(A) Syntactic meta language
(B) Decidable language
(C) Intermediate language
(D) High level language

2. Consider the following language,

L = {anbn|n = 1}

L is?

(A) CFL but not regular
(B) CSL but not CFL
(C) Regular
(D) Type 0 language but not type 1

3. Can a DFSA simulate a NFSA
(A) No
(B) Yes
(C) Sometimes
(D) Depends on NFA

4. A language L is accepted by a FSA if it is
(A) CFL
(B) CSL
(C) Recursive
(D) Regular

5. Recursively enumerable languages are not closed under
(A) Union
(B) Homomorphism
(C) Complementation
(D) Concatenation

6. Grammar

S —> a,
S —> A3A,
A3 —> A1, A3, A2 ,
A3 —> A1 A2, A1
A2—> aA2A,
A1a —> a A1
A2a —> aA2
A1A4 —> A4a,
A2A4 —> A5a,
A2A5 —> A5a,
A5 —> a
generates

(A) an^2
(B) n2a
(C) 2an
(D) None of these

7. Which one of the following statement 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 Keene closure

8. Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is
(A) Context-free ⊂ right-linear ⊂ context-sensitive
(B) Context-free ⊂ context-sensitive ⊂ right-linear
(C) Context-sensitive ⊂ right-linear ⊂context-free
(D) Right-linear ⊂context-free ⊂context-sensitive

9. The CFG

s---> as | bs |  a |  b

Is equivalent to regular expression?

(A) (a + b)
(B) (a + b) (a + b)*
(C) (a + b) (a + b)
(D) None of these

10. Consider the following language,

L = {anbncndn|n = 1}

L is?

(A) CFL but not regular
(B) CSL but not CFL
(C) Regular
(D) Type 0 language but not type 1

Show and hide multiple DIV using JavaScript View All Answers

Next Tests:
Blogger Comment