Which of the following is pumped to generate further strings in the definition of Pumping Lemma?

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

The CFG S --> aSa | bSb | a | b | ^ represents the language ___.

• A) EVEN-EVEN
• B) PALINDROM
• C) EQUAL
• D) ODD-ODD

Finite Automaton (FA) must have __________ number of states while a language has _________ words.

• A) infinite, infinite
• B) infinite, finite
• C) finite, finite
• D) finite, infinite

Halt states are ___.

• A) Start and Accept
• B) Accept and Reject
• C) Start and Reject
• D) Read and Reject

Which of the following refers to the set of strings of letters that when concatenated to the front of some word in Q produces some word in R?

• A) Pref(R in Q)
• B) Postf(R in Q)
• C) Postf(Q in R)
• D) Pref(Q in R)

The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by ______ production tree(s).

• A) More than one
• B) At most one
• C) Zero
• D) One

The unit and null productions can be deleted from a CFG.

• A) True
• B) False
• C) Only null
• D) None of given

If R is regular language and Q is any language (regular/ non-regular), then Pref( _______in _______) is regular.

• A) R,Q
• B) Q,R
• C) Q,Q
• D) R,R

If a language is regular it must generate ____________ number of distinct classes.

• A) two
• B) three
• C) finite
• D) infinite

Set of all palindromes over {a,b} is:

• A) Regular and infinite
• B) Regular
• C) Non-regular
• D) Regular and finite

A problem is said to be _________ if there exists an algorithm that provides the solution in __________ number of steps.

• A) effectively solvable, infinite
• B) effectively solvable, finite
• C) effectively unsolvable, finite
• D) effectively unsolvable, infinite

The production of the form: nonterminal to one nonterminal is called the ___.

• A) Unit production
• B) NULL production
• C) Terminal production
• D) Non Terminal production

Prime is a ______________ language.

• A) finite
• B) regular
• C) both context free and regular
• D) non-regular

If Q = {xx, xyxxxy }, and R = {xyxyxyxxyy, xyxyyyxx} then Pref( Q in R) = ____________

• A) xyxyyy
• B) xx
• C) xxy
• D) xyxyxy

The operators like (* , +) in the parse tree are considered as ________.

• A) productions
• B) terminals
• C) non-terminals
• D) intermediates

A non regular language can be represented by

• A) None of the given options
• B) FA
• C) TG
• D) RE

Which of the following cannot be represented by a regular expression?

• A) String of 0’s with a prime length
• B) Language of even-even
• C) String of 0’s with an odd length
• D) Language of odd-odd

Even-Even language partitions ∑* into ___________ distinct classes.

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

The language of all strings not beginning with ‘b’ partitions ∑* into ___________distinct classes.

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

The production S --> SS | a | b | ^ can be expressed by Regular expression _________.

• A) (ab)*
• B) (a+b)
• C) (a+b)*
• D) (a+b)+