If Σ = {aa bb} then Σ* will not contain ___.

• A) aaabbb
• B) aabbbb
• C) aabbaa
• D) bbaabbbb

One language can have ___ TG's.

• A) Only one
• B) Only two
• C) More than one
• D) Only three

According to 1st part of the Kleene's theorem if a language can be accepted by an FA then it can be accepted by a ___ as well.

• A) FA
• B) CFG
• C) GTG
• D) TG

Even-palindrome is a ___ language.

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

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

• A) Regular
• B) Non-regular
• C) Regular but finite
• D) None of the given

Pumping lemma is generally used to prove that:

• A) A given language is infinite
• B) A given language is not regular
• C) Whether two given regular expressions are equivalent or not
• D) None of these

If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will ___ word/words.

• A) accept all
• B) accept no
• C) accept some
• D) reject no

In CFG the symbols that can't be replaced by anything are called ___.

• A) Terminal
• B) Non-Terminal
• C) Production
• D) All of given

Which of the following is a regular language?

• A) String of odd number of zeroes
• B) Set of all palindromes made up of 0's and 1's
• C) String of 0's whose length is a prime number
• D) All of these

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