# 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

- (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

Show and hide multiple DIV using JavaScript

- (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

**View All Answers****Next Tests:**