All possible combinations of strings of a language including null string is referred as:

• A) Addition of a language with itself
• B) Subtraction of a language with itself
• C) Concatenation of a language with itself
• D) Kleene star closure of a language

The process of finding the derivation of the word generated by particular grammar is called ___.

• A) Processing
• B) Parsing
• C) Programming
• D) Planning

Keeping in view the discussion by Martin, how many states are required to recognize the language of all strings of length 2 or more defined over ∑= {a,b}, with ‘b’ being the second letter from right?

• A) 9
• B) 8
• C) 6
• D) 7

The first rule of converting the given CFG in CNF is ___.

• A) CNK algorithm
• B) CYK algorithm
• C) CKY algorithm
• D) KYC algorithm

A loop at a state is supposed to be ---------- transition while converting Moore machine into an equivalent Melay machine.

• A) Incoming
• B) Complex
• C) Outgoing
• D) Both incoming and outgoing

The language L defined over Σ, not belonging to L, is called _______ of the language L.

• A) closure
• B) intersection
• C) union
• D) complement

We cannot write regular expressions for all ___.

• A) FA's
• B) TG's
• C) NFA's
• D) CFG's

In the context of make NFA for the concatenation of FA1 and FA2 (FA2 accepting null string), which of the following option is correct?

• A) FA2 having final state only
• B) FA2 having initial state only
• C) Initial states in both FAs
• D) Final states in both FAs

For every Context Free Grammar (CFG) we can make the corresponding ___.

• A) FA
• B) TG
• C) PDA
• D) Regular Grammar

Considering FA1 and FA2 having 2 states each. Now FA1+FA2 can have maximum ______________ number of states.

• A) more than 3
• B) None of the given options
• C) 2
• D) 3

Pumping Lemma II says that length(x) + length(y) should be ___.

• A) Less than number of states
• B) Equal to number of states
• C) Greater than number of states
• D) Greater than or equal to number of states

In Moore machine, output is produced over the change of:

• A) Transitions
• B) States
• C) Transitions and states
• D) None of the mentioned

Chomsky normal form (CYK) algorithm was proposed by ___.

• A) John cock
• B) James Cock
• C) Daniel I.A.
• D) John Weiss

In the context of make NFA for the concatenation of FA1 and FA2 (FA1 accepting null string), which of the following option is correct?

• A) FA2 having final state only
• B) Final states in both FAs
• C) Initial states in both FAs
• D) FA2 having initial state only

The language of Palindromes defined over an alphabet set {a b} can be recognized by ___.

• A) FA
• B) NFA
• C) TG
• D) PDA

If new A =1 NAND ( 1 AND 1), then what will be the value of new A?

• A) 10
• B) 1
• C) 0
• D) 01

Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of

• A) FA1 or FA2
• B) FA1 and FA2
• C) FA2 only
• D) FA1 only

(Σ* - L) represent the ___ of a language L.

• A) Complement
• B) Kleene's closure
• C) Union
• D) intersection

Two machines are said to be equivalent if they print the _____ output string when the _____input string is run on them.

• A) unique, different
• B) different, same
• C) same, same
• D) same, different

If we have two transition graphs then their union will be expressed by ___.

• A) taking a common start state and joining them by two null transitions
• B) just connecting both start states by null transitions
• C) connecting final state of first TG to the initial state of second TG
• D) connecting the final state of first TG to the final state of second TG