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

NFA corresponding to union of FAs is built by introducing a new start state and connect it to the states originally connected to the old start state with the --------- transitions as the old start state:

• A) Different
• B) Union of
• C) Concatenated
• D) Same

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

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

• A) 16
• B) 15
• C) 14
• D) 13

Like TG a PDA can also be non-deterministic.

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

If we have input 110010111 and the machine generates the 001101000 as an output, then that machine will be called?

• A) Mealy machine
• B) Moore machine
• C) Complementing machine
• D) Incrementing machine

Let L be the language of all strings, defined over Σ = {0,1}, ending in 10. Which of the following strings are distinguishable with respect to L with z being 0?

• A) 111, 101
• B) 001, 101
• C) 010, 101
• D) 111, 111

If L1 and L2 are two regular languages, then L1 Intersection L2 is:

• A) Finite
• B) Infinite
• C) Regular
• D) Irregular

Which of the following statements is true about NFA with Null String?

• A) Infinite set of transitions
• B) Infinite states
• C) Infinite set of letters
• D) Transition of null string is allowed at any stage

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

What will be the 9’s complement of the number 872?

• A) 127
• B) 271
• C) 172
• D) 721

FA corresponding to an NFA can be built by introducing an empty state for a letter having

• A) two transitions at certain state
• B) no transition at certain state
• C) one transition at certain state
• D) more than two transitions at certain state