If L1 and L2 are regular languages then which statement is NOT true?

• A) L1/L2 is always regular
• B) L1 + L2 is always regular
• C) L1 L2 is always regular
• D) L1* is always regular

___ 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

In which of the following machine, the length of output string is the same to that of input string?

• A) Finite automaton with output
• B) Moore machine
• C) Non-deterministic finite automaton
• D) Mealy machine

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

The language {a, ab, aba, bab} is __________ .

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

Which one of the following machine is represented as a pictorial representation with states and directed edges labeled by an input letter along with an output character?

• A) Mealy machine
• B) Finite state machine
• C) Moore machine
• D) Deterministic finite state machine

A read state can have ___ outgoing edge/edges.

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

Which of the following machine has only one initial state and no final state?

• A) Non deterministic finite state machine
• B) Moore machine
• C) Deterministic finite state machine
• D) Finite state machine

Who did not invent the Turing machine?

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

The minimum length of the strings(except null string) of a language that starts and ends in different letters will be:

• A) 4
• B) 2
• C) 3
• D) 1

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

In NFA having no transition at certain state, FA can be built by introducing:

• A) Final state
• B) Combination of states
• C) Initial state
• D) Empty state

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

The minimum length of the strings(except null string) of a language that starts and ends in the same letters will be:

• A) 2
• B) 1
• C) 4
• D) 3

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

There ______ a language for which only FA can be built but not the RE.

• A) cannot be
• B) may be
• C) is
• D) can be

If we have only one state, having no transition for input letters, then it is an example of:

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

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

The complement of a regular language is also __________.

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

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