If L is a regular language then ___ is also a regular language.

• A) Lm
• B) Ls
• C) Lx
• D) Lc

In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.

• A) Always easy
• B) may be good
• C) always impossible
• D) Impossible

In a CFG, the non-terminals are denoted by _________.

• A) Small letters
• B) Small letters and numbers
• C) Numbers
• D) Capital letters

For a machine with N number of states, the total number of strings to be tested, defined over an alphabet of m letters, is _____________.

• A) mN
• B) Nm +Nm+1+ N m+2 +… + N2m-1
• C) mN +mN+1+ mN+2 +… +m2N-1
• D) Nm

A language ending with ‘b’ partitions ∑* into ___________distinct classes.

• A) four
• B) three
• C) two
• D) five

For a non-regular language, there exists ___________ FA.

• A) at least one
• B) at most one
• C) no
• D) one

Using Myhill Nerode theorem we partition sigma star into distinct __________.

• A) instances
• B) objects
• C) classes
• D) templates

Let L be any infinite regular language defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ* such that all the strings of the form xy^n z for n=1,2,3 are the words in L. This is called ___.

• A) Complement of L
• B) Pumping Lemma
• C) Kleene's theorem
• D) None in given

If an effectively solvable problem has answer in YES or NO, then the solution is called _________.

• A) decision procedure
• B) optimal procedure
• C) infinite problem
• D) finite solution

Which of the following should not be NULL in the context of Pumping Lemma?

• A) y
• B) z
• C) x
• D) n

If L1 and L2 are two regular languages, then they _______ expressed by FAs.

• A) can be
• B) May be
• C) cannot be
• D) may or may not be

Which of the following is a non-regular language?

• A) Even-Even
• B) Odd-Odd
• C) Language of strings ending in abba
• D) Prime

One language can have ______ CFG(s).

• A) At least one
• B) More than one
• C) Only one
• D) At most one

There is at least one production in CFG that has one _________ on its left side.

• A) Terminal
• B) Unit production
• C) Null production
• D) Non terminal

To write the expression from the tree, it is required to traverse from ___________.

• A) Right side of the tree
• B) Left side of the tree
• C) Bottom to top of the tree
• D) Top to bottom of the tree

In pumping lemma theorem (x y^n z) the range of n is

• A) n=…….-3,-2,-1, 0, 1, 2, 3, 4……
• B) n=1, 2, 3, 4……….
• C) n=0, 1, 2, 3, 4……….
• D) n=…….-3,-2,-1, 1, 2, 3, 4……

The language of all strings partition ∑* into ___________ class(es).

• A) one
• B) three
• C) two
• D) four

In pref(Q in R), Q is _______ to/than R.

• A) Not equal
• B) Equal
• C) Greater
• D) Smaller

If A→ B and CB → D, then AC → D. 1. The above rule follows _____________ inference rule.

• A) Additivity
• B) Pseudo transitivity
• C) Augmentation
• D) Decomposition

An attribute y may be functionally dependent on
(i) a composite attribute x,y
(ii) a single attribute x
(iii) no attribute

• A) i and ii
• B) i and iii
• C) iii
• D) ii and iii