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

Moore Machine is an application of:

• A) None of the mentioned
• B) Finite automata without input
• C) Finite automata with output
• D) Non- Finite automata with output

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

In which of the following machine, the length of output string is 1 more than that of input string?

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

PDA is only used to represent a regular language.

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

The length of output string in case of _________ is one more than the length of corresponding input string.

• A) Incremental machine
• B) Adding Machine
• C) Mealy machine
• D) Moore machine

In Moore machine, if the length of input string is 9, then the length of output string will be:

• A) 8
• B) 9
• C) 7
• D) 10

We can find a CFG corresponding to a DFA.

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

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

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

NFA with null string has ---------- initial state(s).

• A) Many
• B) One
• C) Two
• D) Three