FA corresponding to an NFA can be built by introducing an empty state for a letter having ___.

• A) no transition at certain state
• B) one transition at certain state
• C) two transition at certain state
• D) more than two transitions at certain state

In order to make NFA for the union of FA1 and FA2, the new initial state should be linked to:

• A) initial and final states of FA1 and FA2 respectively
• B) final and initial states of FA1 and FA2 respectively
• C) initial states of both FAs
• D) initial state of FA1 only

FA corresponding to an NFA can be built by introducing a state corresponding to the combination of states, for a letter having

• A) more than one transitions at certain state
• B) one transition at certain state
• C) none of the given options
• D) no transition at certain state

FA and _______ are same except that _______ has unique symbol for each transition.

• A) GTG,NFA
• B) NFA,FA
• C) NFA,TG
• D) FA,TG

Which of the following state is introduced while developing NFA for the closure of an FA?

• A) An initial state which should be final as well
• B) An initial state with loop for all letters
• C) Simply an initial state
• D) Final state

In order to make NFA for the union of FA1 and FA2, the final state/ states of:

• A) FA2 have a transition to the final state of FA1
• B) both FAs should be left intact
• C) FA1 have a transition to the final state of FA2
• D) both FAs should be linked

The product of two regular languages is __________.

• A) infinite
• B) regular
• C) non-regular
• D) closure of a regular language

A PDA is called nondeterministic PDA if ___.

• A) There are more than one outgoing edges at READ or POP states with one label
• B) There are more than one PUSH states
• C) There are more than one POP states
• D) All of the given options

A language that can be expressed by RE, is said to be a _______ language.

• A) finite
• B) regular
• C) irregular
• D) infinite

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