An alphabet of Σ is valid if ___.

• A) No letter of Σ appears in middle of any other letter
• B) No letter of Σ appears at end of any other letter
• C) No letter of Σ appears at start of any other letter
• D) No letter of Σ appears at end or middle of any other letter

If a CFG has only productions of the form nonterminal to string of two nonterminals or nonterminal to one terminal, then the CFG is said to be in ___.

• A) Chomsky Normal Form
• B) Ambiguous Form
• C) Left Aligned Form
• D) Right Aligned Form

We can also represent an FA using different states. The ___ state behaves as final state of an FA.

• A) Accept
• B) Pop
• C) Push
• D) Reject

Where the input string is placed before it is run is called ___.

• A) Date tape
• B) Input Tape
• C) Output Tape
• D) Magnetic tape

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

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

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

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

We cannot write regular expressions for all ___.

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

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

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

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

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

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

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

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

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

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

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

___ and ___ are removed in order to make a CFG in Chomsky Normal Form (CNF).

• A) Null and nullable productions
• B) Nullable and unit productions
• C) Null and unit productions
• D) String of length 0 and null

If L1 and L2 are expressed by regular languages then L1 + L2 is also a ___ Language.

• A) Regular
• B) Ir-regular
• C) PDA
• D) Hybrid

A read state can have ___ outgoing edge/edges.

• A) 1
• B) 2
• C) 3
• D) Any number of

Who did not invent the Turing machine?

• A) Alan Turing
• B) A. M. Turing
• C) Turing
• D) None of these

Which statement is true?

• A) The tape of turing machine is infinite
• B) The tape of turing machine is finite
• C) The tape of turing machine is infinite when the language is regular
• D) The tape of turing machine is finite when the language is nonregular

Every regular expression can be expressed as CFG but every CFG cannot be expressed as a regular expression. This statement is:

• A) Depends on the language
• B) None of the given options
• C) True
• D) False

Consider the language L of strings defined over Σ = {a b} ending in a ___.

• A) There are finite many classes generated by L so L is regular
• B) There are infinite many classes generated by L so L is regular
• C) There are finite many classes generated by L so L is non-regular
• D) There are infinite many classes generated by L so L is non-regular