(Σ* - 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

Let A = {0 1}. The number of possible strings of length n that can be formed by the elements of the set A is ___.

• A) n!
• B) n^2
• C) n^m
• D) 2^n

Choose the correct statement.

• A) A Mealy machine generates no language as such
• B) A Moore machine generates no language as such
• C) A Mealy machine has no terminal state
• D) All of these

TM is more powerful than FSM because ___.

• A) The tape movement is confined to one direction
• B) It has no finite state control
• C) It has the capability to remember arbitrary long sequences of input symbols
• D) None of these

Like TG a PDA can also be non-deterministic.

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

Which of the following is NOT a regular language?

• A) String of 0's whose length is a perfect square
• 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 the given options

Left hand side of a production in CFG consists of:

• A) One terminal
• B) More than one terminal
• C) One non-terminal
• D) Terminals and non-terminals

PDA is only used to represent a regular language.

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

We can find a CFG corresponding to a DFA.

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

A CFG is said to be ambiguous if there exists at least one word of its language that can be generated by different production trees.

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

Syntax tree or Generation tree or Derivation tree are same tree.

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

The production of the form non-terminal to one non-terminal is called unit production.

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